(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

Solutions for Problems 1-40

Solutions: [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]

Solutions to Problem 1

Problem: Find all positive integers n such that n^2+1 is divisible by n+1.
Solution [Fred's - Jun 99]:
If n+1 | n^2 + 1 then n^2 + 1 - (n-1)(n+1) = n^2+1 - (n^2-1) = 2 must be divisible by n+1. The factors of 2 are 'sumdiff(,1) and 'sumdiff(,2). These values for n+1 yield n = _3, _2, 0 or 1. Only the last, n=1, is a positive integer as required.
Solution from Book:
There is only one such positive integer: n=1. In fact, n^2+1 = n*(n+1)-(n-1); thus, if n+1 | n^2+1, then n+1 | n-1 which for positive integer n is possible only if n-1 = 0, hence n=1.

Solutions to Problem 2

Problem: Find all integers x != 3 such that x-3 | x^3 - 3.
Solution [Fred's - Jun 99]:
If x-3 | x^3 - 3 then x-3 | (x^3-3)-(x-3)^3 = 9*x^2 - 27*x + 24. Continuing, x-3 | 9*x^2-27*x+24 - 9(x-3)^2 ; (x-3) | 27*x+105 ; x-3 | 27*x+105 - 27*(x-3) ; (x-3) = _24. The possible values of x-3 are the factors of _24: 'sumdiff(,1), 'sumdiff(,2), 'sumdiff(,3), 'sumdiff(,4), 'sumdiff(,6), 'sumdiff(,8), 'sumdiff(,12) and 'sumdiff(,24). These yield the solutions x = _21, _9, (_3), (_1), 0, 1, 2, 3, 4, 5, 6, 7, 9, 15, 27.
Solution from Book:

Solutions to Problem 3

Problem: Prove that there exists infinitely many positive integers n such that 4*(n^2)+1 is divisible both by 5 and 13.
Solution [Fred's - Jun 99]:
By inspection of the first few values n=1,2,3,4, 'ellipsis we find 4*(4^2)+1 is divisible by 65 (hence by both 5 and 13). Having found one value, consider (the infinitely many) numbers of the form n=65*k+4 where k>=0; when these are squared, the result is of the form n^2=65*j+4^2, so 4*n^2+1=4*65*j+4^3+1=65*(4*j+1) is divisible by both 5 and 13 as required.
Solution from Book:

Solutions to Problem 4

Problem: Prove that for positive integers n we have 169 | 3^(3*n+3) - 26*n - 7.
Solution [Fred's - Jun 99]:
Use induction. Let f(n)=3^(3*n+3)-26*n-27. It's easily verified that 169|f(_1) and 169|f(0). Consider f(n+1)-f(n) = 3^(3*n+6)-3^(3*n+3)-26 = (3^(3*n+3))*(3^3-1)-26 = 26(3^(3*n+3)-1) . Since 'congmod( 3^(3*n+3)-1 = 3^(3*(n+1))-1 = (3^3)^(n+1)-1, 1^(n+1)-1=0, 13) , we have 169 | (f(n+1)-f(n)).


Solution from Book:

Solutions to Problem 5

Problem: Prove that 19 | 2^(2^(6*k+2))+3 for k=0, 1, 2, 'ellipsis
Solution [Fred's - May 2001]:
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)))
2^(2^(6*(k+1)+2)) - 2^(2^(6*k+2)) = (2^(2^(6*k+2))) * ( (2^(2^(6*k+6+2))) - 1 )
(2^(2^(6*k+6+2))) - 1 = 2^(2^(6*k+2) * (2^6 - 1)) - 1 = 2^(63 * 2^(6*k+2)) - 1
n0123456789
2^n mod 191248_3_67_59_1
So 2^(63 * 2^(6*k+2)) - 1 = (2^9)^(7 * 2^(6*k+2)) - 1 = (_1)^(7 * 2 * 2^(6*k+1)) - 1 (mod 19) = 1 - 1 = 0
Solution from Book:

Solutions to Problem 6

Problem: Prove the theorem, due to Kraïtchik, asserting that 13 | 2^70 + 2^30.
Solution [Fred's - May 2001]:
n0123456
2^n mod 13124_536_1
3^n mod 1313_41   
'congmod( 2^70 = (2^(6*11+4)) = (2^(6*11))*(2^4), ((_1)^11 * (2^4)) = (_1 * 3) = (_3), 13 )
'congmod( 3^70 = (3^(3*23+1)) = ((3^3)^23)*3, (1^23) * 3 = (1*3) = 3, 13 )
So 'congmod( 2^70 + 3^70, (_3 + 3) = 0, 13 )
Solution from Book:

Solutions to Problem 7

Problem: Prove that 11 * 31 * 61 | 20^15-1.
Solution [Fred's - May 2001]:
n012345 
20^n mod 111_2_40
= 4		80
= 3		60
= 5		100
= 1		So 'congmod( 20^15 = (20^5)^3, 1^3 = 1, 11 )
20^n mod 31120
= _11		_220
= _3		_60
= 2		  So 'congmod( 20^15 = (20^3)^5, 2^5 = 32 = 1, 31 )
20^n mod 6112040
= _27		_540
= 9		180
= _3		_60
= 1		So 'congmod( 20^15 = (20^5)^3, 1^3 = 1, 61 )

Solution from Book:

Solutions to Problem 8

Problem: Prove that for positive integer m and a > 1 we have gcd ( (a^m-1) / (a-1) , a-1) = gcd ( a-1,m ).
Solution [Fred's - May 2001]:
gcd ( (a^m-1) / (a-1) , a-1) = gcd ( a^(m-1) + a^(m-2) + 'ellipsis + a + 1, a-1 ). 'congmod(a, 1, a-1). 'congmod(a^2 = a * 1, 1, a-1).
So gcd ( (a^(m-1)) + (a^(m-2)) + 'ellipsis + a + 1, a-1 ) = gcd ( 1 + 1 + 'ellipsis + 1 + 1, a-1 ) = gcd ( m * 1, a-1 ) = gcd ( m, a-1 ) .
Solution from Book:

Solutions to Problem 9

Problem: 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.
Solution [Fred's - May 2001]:

Solution from Book:

Solutions to Problem 10

Problem: Find all integers n > 1 such that 1^n + 2^n + 'ellipsis + (n-1)^n is divisible by n.
Solution [Fred's - May 2001]:
Case 1: When n is odd, say n = 2*k+1 for k >= 1,
'Sum(j^n,j,1,n-1) =1^n + 2^n + 'ellipsis + k^n + (k+1)^n + 'ellipsis + (2*k-1)^n + (2*k)^n
 'congmod(,1^n + 2^n + 'ellipsis + k^n + (_k)^n + 'ellipsis + (_2)^n + (_1)^n,n)
 'congmod(,1^n + 2^n + 'ellipsis + k^n - k^n - 'ellipsis - 2^n - 1^n,n)
 'congmod(,0,n)
Case 2: When n is even, say n = 2*k,
'Sum(j^n,j,1,n-1) =1^n + 2^n + 'ellipsis + (k-1)^n + k^n + (k+1)^n + 'ellipsis + (2*k-2)^n + (2*k-1)^n
 'congmod(,1^n + 2^n + 'ellipsis + (k-1)^n + k^n + (k-1)^n + 'ellipsis + (_2)^n + (_1)^n,n)
 'congmod(,2*'Sum(j^n,j,1,k-1) + k^n,n)
Case 2a: When k is odd, 2*'Sum(j^n,j,1,k-1) + k^n is odd, and so is not divisible by any even number, including n.
Case 2a: When k is even, say k=2*m , n=4*m,
2*'Sum(j^n,j,1,k-1) + k^n=2*(1^n + 2^n + 'ellipsis + (2*m-1)^n) + (2*m)^n
 =2*(odd + even + 'ellipsis + odd) + (2*m)^(4*m)
  There are m odd terms in the parenthesised expression, so the expression has the form 2 * odd + 4 * something, which is not divisible by 4, and therefore not divisible by n which is a multiple of 4.

Solution from Book:

Solutions to Problem 11

Problem: 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.
Solution [Fred's - May 2001]:
n01234 
2^n mod 512_1_21
2^(2*n) = (2^n)^2 mod 51_11_11
2^(2*n+1) mod 52_22_22
2^(n+1) mod 52_1_212
a;n mod 5100_215 | a;n if 'congmod(n,1,4) or 'congmod(n,2,4)
b;n mod 50_21005 | b;n if 'congmod(n,0,4) or 'congmod(n,3,4)

Solution from Book:

Solutions to Problem 12

Problem: 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
Solution [Fred's - May 2001]:
Since n|x+1, 'congmod(x+1, 0, n), i.e. 'congmod(x, _1, n).
Since n|x^x+1, 'congmod(x^x+1, 0, n), i.e. 'congmod(x^x = (_1)^x,_1,n). Since 'congmod((_1)^x,_1,n), x must be odd.
So, let x be any odd integer with 'congmod(x, _1, n). There are an infinite number of such x's. Then 'congmod(x^(x^'ellipsis) + 1, (_1)^odd + 1 = 0, n)
Solution from Book:

Solutions to Problem 13

Problem: 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.
Solution [Fred's - May 2001]:
If x is even then all of the terms in the sequence are odd, i.e. not divisible by any even number. So, for any (of the infinitely many) even n, none of the terms of the sequence are divisible by n for even x.
Solution from Book:

Solutions to Problem 14

Problem: Prove that for positive integer n we have n^2 | (n+1)^n - 1.
Solution [Fred's - May 2001]:
'congmod(n+1,n+1,n^2)
'congmod((n+1)^2, n^2+2*n+1 = 2*n+1,n^2)
'congmod((n+1)^3, 2*n^2 + 2*n + n + 1 = 3*n+1,n^2)
If 'congmod((n+1)^k, k*n+1,n^2) (true for k=1, 2, 3)
then 'congmod((n+1)^(k+1), (k*n+1)*(n+1) = k*n^2+k*n+n+1 = (k+1)*n+1,n^2),
so true for all k. So 'congmod((n+1)^(n) - 1, n*n + 1 - 1 = n^2 = 0,n^2)
Solution from Book:

Solutions to Problem 15

Problem: Prove that for positive integer n we have (2^n-1)^2 | 2^((2^n-1)*n) - 1.
Solution [Fred's - May 2001]:
We know x^2 | (x+1)^x - 1 (problem 14). Set x - 2^n-1. Then
(2^n-1)^2 | (2^n-1+1)^(2^n-1)-1
(2^n-1)^2 | (2^n)^(2^n-1)-1
(2^n-1)^2 | 2^(n*(2^n-1))-1 as required.
Solution from Book:

Solutions to Problem 16

Problem: Prove that there exist infinitely many positive integers n such that n | 2^n+1 ; find all such prime numbers.
Solution [Fred's - May 2001]:
For a prime p, 'congmod(a^(p-1), 1, p) if gcd(a,p) = 1 (Fermat's Little Theorem) ; 'congmod(2^(p-1), 1, p) for all odd primes p ; 'congmod(2^p + 1, 2 * 1 + 1 = 3, p). So n | 2^n + 1 for prime n only where 'congmod(3, 0, n), i.e. only for n=3.

If n is even, it doesn't divide 2^n+1, which is odd.

That leaves odd composites. Checking the first few values:

n915212527
2^n+1 mod n(2^3)^3+1
= (_1)^3+1
= 0		(2^4)^3*2^3+1
= 1^3*2^3+1
= 9		(2^5)^4*2+1
= 11^4*2+1
= (_5)^2*2+1
= 9		(2^5)^5+1
= 7^5+1
= (7^2)*7+1
= (_1^2)*7+1
= 8		(2^5)^5*2^2+1
= 5^5*2^2+1
= (5^2)^2*5*2^2+1
= (_2)^2*5*4+1
= 81 = 0
Hmm ... I suspect 3^k | 2^(3^k) + 1. True for k = 1, 2, 3. If true for k, i.e. 'congmod(2^(3^k), _1, 3^k), say 2^(3^k) = m * 3 ^ k - 1, then
2^(3^(k+1)) = 2^(3^k*3)=(m*3^k-1)^3
=m^3*3^(3*k) - 3*m^2*3^(2*k) + 3*m*3^k - 1
=3*3^k*('ellipsis - 'ellipsis + 'ellipsis) - 1
=3^(k+1)*('ellipsis - 'ellipsis + 'ellipsis) - 1
'congmod(,_1,3^(k+1))
So true for all k ; n = 3^0, 3^1, 3^2, 'ellipsis is an infinite sequence of solutions, as required.
Outstanding problem: What are all solutions, i.e. what (if any) are the remaining composite n satisfying n | 2^n+1 ?
Solution from Book:

Solutions to Problem 17

Problem:
Solution [Fred's - May 2001]:

Solution from Book:

Solutions to Problem 18

Problem:
Solution [Fred's - May 2001]:

Solution from Book:

Solutions to Problem 19

Problem: Find all positive integers a for which a^10+1 is divisble by 10.
Solution [Fred's - May 2001]:
We only have to check values of a modulo 10. If a is even, then a^10+1 is odd and not divisible by a.
a mod 10a^10+1 mod 10
'sumdiff(,1)1+1=2
'sumdiff(,3)9+1=0
'sumdiff(,5)6+1=0
So the answer is 'congmod(a, 'sumdiff(,3), 10)
Solution from Book:

Solutions to Problem 20

Problem:
Solution [Fred's - May 2001]:

Solution from Book:

Solutions to Problem 20a

Problem: Prove that there exist infinitely many positive integers n such that n|2^n+1.
This problem is a subset of problem 16.
Solution [Fred's - May 2001]:
This problem is a subset of problem 16.
Solution from Book:

Solutions to Problem 21

Problem: Find all odd n such that n|3^n+1.
Solution [Fred's - May 2001]:

Solution from Book:

Solutions to Problem 22

Problem: Find all positive integers n such that 3|n^2^n+1.
Solution [Fred's - May 2001]:

Solution from Book:

Solutions to Problem 23

Problem: Prove that for every off prime p there exist infinitely many positive integers n such that p|n*2^n+1.
Solution [Fred's - May 2001]:

Solution from Book:

Solutions to Problem 24

Problem:
Solution [Fred's - May 2001]:

Solution from Book:

Solutions to Problem 25

Problem:
Solution [Fred's - May 2001]:

Solution from Book:

Solutions to Problem 26

Problem:
Solution [Fred's - May 2001]:

Solution from Book:

Solutions to Problem 27

Problem:
Solution [Fred's - May 2001]:

Solution from Book:

Solutions to Problem 28

Problem:
Solution [Fred's - May 2001]:

Solution from Book:

Solutions to Problem 29

Problem:
Solution [Fred's - May 2001]:

Solution from Book:

Solutions to Problem 30

Problem:
Solution [Fred's - May 2001]:

Solution from Book:

Solutions to Problem 31

Problem:
Solution [Fred's - May 2001]:

Solution from Book:

Solutions to Problem 32

Problem:
Solution [Fred's - May 2001]:

Solution from Book:

Solutions to Problem 33

Problem:
Solution [Fred's - May 2001]:

Solution from Book:

Solutions to Problem 34

Problem: Prove that if for integers a and b we have 7|a^2+b^2 then 7|a and 7|b.
Solution [Fred's - May 2001]:
n mod 70'sumdiff(,1)'sumdiff(,2)'sumdiff(,3)
n^2 mod 70142
The only pair of values of a and b which yield 'congmod(a^2+b^2,0,7) are 'congmod(a=b,0,7), i.e. 7|a and 7|b.
Solution from Book:

Solutions to Problem 35

Problem:
Solution [Fred's - May 2001]:

Solution from Book:

Solutions to Problem 36

Problem:
Solution [Fred's - May 2001]:

Solution from Book:

Solutions to Problem 37

Problem:
Solution [Fred's - May 2001]:

Solution from Book:

Solutions to Problem 38

Problem:
Solution [Fred's - May 2001]:

Solution from Book:

Solutions to Problem 39

Problem: 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.
Solution [Fred's - May 2001]:
It's just as easy to prove a generalization. Let x;1, 'ellipsis, x;m be integers, n > m. Then taking the x;i modulo n yields at most m < n distinct values. Choose a value j such that for any i, j != x;i modulo n. Set k=_j. Then none of the numbers (x;1)+k, (x;2)+k, 'ellipsis, (x;m)+k are divisible by n.
Solution from Book:

Solutions to Problem 40

Problem:
Solution [Fred's - May 2001]:

Solution from Book:
-This page
last changed:
4 Sep 2002
[Validate HTML]
-Donate free
food & land		 
-
|Feedback by email
or Web form