(You can invoke Ping's MINSE polymediator to render the maths expressions on this page.)
-Up to-Home/Maths/250 Problems In Elementary Number Theory/Prob1-40
-Site Map|-Text version

Hints for Problems 1-40

These pages contain hints for problems from Section 1 - "Divisibility of Numbers" of the book "250 Problems In Elementary Number Theory"

Hints: [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [20a] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40]

Hint for Problem 1
Problem 1 was: Find all positive integers n such that n^2+1 is divisible by n+1.
Hint: n^2-1 is always divisible by n+1
[Solution for Problem 1]
Hint for Problem 2
Problem 2 was: Find all integers x != 3 such that x-3 | x^3 - 3.
Hint: Use the powers of x-3 to obtain polynomials of same/lesser degree than x^3-3 which must be divisible by x-3. Take a look at solution to problem 1. What's the expansion of (x-3)^3 ?
[Solution for Problem 2]
Hint for Problem 3
Problem 3 was: Prove that there exists infinitely many positive integers n such that 4*(n^2)+1 is divisible both by 5 and 13.
Hint: Are there any small values of n for which 4*n^2+1 is divisible by 65 (and hence by both 5 and 13)? Having found a value of n, try ?(n") = n+65 ; does that work?
[Solution for Problem 3]
Hint for Problem 4
Problem 4 was: Prove that for positive integers n we have 169 | 3^(3*n+3) - 26*n - 7.
Hint: Use induction. Let f(n)=3^(3*n+3)-26*n-27. Does 169 | f(n+1)-f(n)?
[Solution for Problem 4]
Hint for Problem 5
Problem 5 was: Prove that 19 | 2^(2^(6*k+2))+3 for k=0, 1, 2, 'ellipsis
Hint: True for k=0 since 2^(2^(6*0+2))+3 = 2^(2^2)+3 = 2^4+3 = 19
True for all k if 19 | (2^(2^(6*(k+1)+2)) - 2^(2^(6*k+2)))

[Solution for Problem 5]
Hint for Problem 6
Problem 6 was: Prove the theorem, due to Kraïtchik, asserting that 13 | 2^70 + 2^30.
Hint: Work out some small powers of 2 and 3 taken modulo 13.
[Solution for Problem 6]
Hint for Problem 7
Problem 7 was: Prove that 11 * 31 * 61 | 20^15-1.
Hint: Work out some small powers of 20 taken modulo 11, 31, 61.
[Solution for Problem 7]
Hint for Problem 8
Problem 8 was: Prove that for positive integer m and a > 1 we have gcd ( (a^m-1) / (a-1) , a-1) = gcd ( a-1,m ).
Hint: What's a modulo a-1? What's a^2 modulo a-1? What's a^x modulo a-1?
[Solution for Problem 8]
Hint for Problem 9
Problem 9 was: Prove that for every positive integer n the number 3 * (1^5 + 2^5 + 'ellipsis + n^5) is divisible by 1^3 + 2^3 + 'ellipsis + n^3.
Hint:
[Solution for Problem 9]
Hint for Problem 10
Problem 10 was: Find all integers n > 1 such that 1^n + 2^n + 'ellipsis + (n-1)^n is divisible by n.
Hint: What happens when n is even? When n is odd?
[Solution for Problem 10]
Hint for Problem 11
Problem 11 was: For positive integer n, find which of the two numbers a subscript n = 2^(2*n+1) - 2^(n+1) +1 and b subscript n = 2^(2*n+1) + 2^(n+1) +1 is divisible by 5 and which is not.
Hint: Make a table of the values 2^n, 2^(n+1), 2^(2*n+1) modulo 5 for some small values of n.
[Solution for Problem 11]
Hint for Problem 12
Problem 12 was: Prove that for every positive integer n there exists a positive integer x such that each of the terms of the infinite sequence x+1, x^x+1, x^(x^x)+1, 'ellipsis is divisible by n
Hint: If n | (x+1), what is x modulo n? What is x^x module n when x is even? odd?
[Solution for Problem 12]
Hint for Problem 13
Problem 13 was: Prove that there exist infinitely many positive integers n such that for every even x none of the terms of the sequence x^x+1, x^(x^x)+1, x^(x^(x^x))+1, 'ellipsis is divisible by n.
Hint: If x is even, which terms of the sequence are even? odd?
[Solution for Problem 13]
Hint for Problem 14
Problem 14 was: Prove that for positive integer n we have n^2 | (n+1)^n - 1.
Hint: What's n+1 modulo n^2? What's (n+1)^2 modulo n^2? What's (n+1)^3 modulo n^2?
[Solution for Problem 14]
Hint for Problem 15
Problem 15 was: Prove that for positive integer n we have (2^n-1)^2 | 2^((2^n-1)*n) - 1.
Hint: Use problem 14, but be careful doing the variable substitution (maybe use another variable besides n).
[Solution for Problem 15]
Hint for Problem 16
Problem 16 was: Prove that there exist infinitely many positive integers n such that n | 2^n+1 ; find all such prime numbers.
Hint: Use Fermat's Little Theorem: For a prime p, 'congmod(a^(p-1), 1, p) if gcd(a,p) = 1.
[Solution for Problem 16]
Hint for Problem 17
Problem 17 was:
Hint:
[Solution for Problem 17]
Hint for Problem 18
Problem 18 was:
Hint:
[Solution for Problem 18]
Hint for Problem 19
Problem 19 was: Find all positive integers a for which a^10+1 is divisble by 10.
Hint:
[Solution for Problem 19]
Hint for Problem 20
Problem 20 was:
Hint:
[Solution for Problem 20]
Hint for Problem 20a
Problem 20a was: Prove that there exist infinitely many positive integers n such that n|2^n+1.
This problem is a subset of problem 16.
Hint:
[Solution for Problem 20a]
Hint for Problem 21
Problem 21 was: Find all odd n such that n|3^n+1.
Hint:
[Solution for Problem 21]
Hint for Problem 22
Problem 22 was: Find all positive integers n such that 3|n^2^n+1.
Hint:
[Solution for Problem 22]
Hint for Problem 23
Problem 23 was: Prove that for every off prime p there exist infinitely many positive integers n such that p|n*2^n+1.
Hint:
[Solution for Problem 23]
Hint for Problem 24
Problem 24 was:
Hint:
[Solution for Problem 24]
Hint for Problem 25
Problem 25 was:
Hint:
[Solution for Problem 25]
Hint for Problem 26
Problem 26 was:
Hint:
[Solution for Problem 26]
Hint for Problem 27
Problem 27 was:
Hint:
[Solution for Problem 27]
Hint for Problem 28
Problem 28 was:
Hint:
[Solution for Problem 28]
Hint for Problem 29
Problem 29 was:
Hint:
[Solution for Problem 29]
Hint for Problem 30
Problem 30 was:
Hint:
[Solution for Problem 30]
Hint for Problem 31
Problem 31 was:
Hint:
[Solution for Problem 31]
Hint for Problem 32
Problem 32 was:
Hint:
[Solution for Problem 32]
Hint for Problem 33
Problem 33 was:
Hint:
[Solution for Problem 33]
Hint for Problem 34
Problem 34 was: Prove that if for integers a and b we have 7|a^2+b^2 then 7|a and 7|b.
Hint: Make a table of squares modulo 7.
[Solution for Problem 34]
Hint for Problem 35
Problem 35 was:
Hint:
[Solution for Problem 35]
Hint for Problem 36
Problem 36 was:
Hint:
[Solution for Problem 36]
Hint for Problem 37
Problem 37 was:
Hint:
[Solution for Problem 37]
Hint for Problem 38
Problem 38 was:
Hint:
[Solution for Problem 38]
Hint for Problem 39
Problem 39 was: Prove that if a, b, c are any integers, and n is an integer () .gt 3, then there exists an integer k such that none of the numbers k+a, k+b, k+c is divisibly by n.
Hint: Use the pigeon-hole principle.
[Solution for Problem 39]
Hint for Problem 40
Problem 40 was:
Hint:
[Solution for Problem 40]
-This page
last changed:
24 May 2001
[Validate HTML]
-Donate free
food & land		 
-
|Feedback by email
or Web form