NUMBER THEORY ASSIGNMENT 1

NUMBER THOERY - 2
1. Prove that for any natural number n, the expression A = 2903n – 803n – 464n + 261n is divisible by
1897.
2. Show that the square of an odd integer is  1 (mod 8)
3. Find the remainder when the number 1010 + 10100 + 101000 + … + 10100000000 is divided by 7.
4. What is the remainder of 1234567894 when it is divided by 8?
5. (i) Find the remainders when 250 and 4165 are divided by 7.
(ii) Find the remainder when 1373 + 143 is divided by 11.
6. (a) Find all positive integers n for which 2n– 1 is divisible by 7.
(b) Prove that there is no positive integer n for which 2n + 1 is divisible by 7.
7. Is it possible for the sum of the first several natural numbers to be 1989?
8. Prove that a power of 2 cannot end with four equal digits.
9. Jerry has 44 boxes of soda in his truck. The cans of soda in each box are packed oddly so that there
are 113 cans of soda in each box. Jerry plans to pack the sodas into cases of 12 cans to sell. After
making as many complete cases as possible, how many sodas will Jerry have leftover?
10. If n! denotes the product of the integers 1 through n, what is the remainder when (1!+ 2! + 3! + 4! +
5! + 6!+...) is divided by 9.
NUMBER THEORY 2

Answers Key
3. 4 4. 1 5. 6; 2 6. n = 3k 7. No 9. 4 10. 0

Solutions
1. Prove that for any natural number n the expression A = 2903n – 803n – 464n + 261n is divisible by
1897
Sol Let n be a natural number. Note that 1897 = 7 × 271.
Consider the expression A = 2903n – 803n – 464n + 261n.
Now 2903  803 (mod 7) and 464  261 (mod 7).
Also 2903  464 (mod 271) and 803  261 (mod 271) .
Hence A is divisible by 7 as well as 271. Since (7,271) = 1,
we get that A is divisible by 1897.
2. Show that the square of an odd integer is  1 (mod 8)
Sol. x  ± 1, ± 3 mod (8)
x2  1,9 mod 8
x2  1 mod 8
3. Find the remainder when the number 1010 + 10100 + 101000 + … + 10100000000 is divided by 7.
Sol. 103  – 1 mod (7)
106 = 1 mod (7)
Also, 10n = 4 mod (6)
10n = 6k + 4
106k + 4  –10  4 mod (7)
1010 + 10100 + .. + 1010000000  32  4 mod (7)
4. What is the remainder of 1234567894 when it is divided by 8?
Sol. 12345789  5 mod (8)
(12345789)4  625  1 mod (8)
5. (i) Find the remainders when 250 and 4165 are divided by 7.
(ii) Find the remainder when 1373 + 143 is divided by 11.
Sol. (i) 23  1 mod (7)
250 = (23)16 ×22  4 mod (7)
4165  (–1)65  6 mod (7)
NUMBER THEORY 3

(ii) We note that 13  2 (mod 11)

1373  273 (25)14 23  (-1)148 (mod 11)  8(mod 11)

Thus 1373  8 (mod11) ..(1)

and 143 33 5 (mod 11) ..(2)
Adding the congruence’s (1) and (2), we get
1373 + 143  8 + 5  2 (mod11)
Hence 2 is the remainder when 1373 + 143 is divided by 11
6. (a) Find all positive integers n for which 2n– 1 is divisible by 7.
(b) Prove that there is no positive integer n for which 2n + 1 is divisible by 7.
Sol. n can be 3k, 3k+1 or 3k+2
(i) When n=3k,
2n = 23k  (1)k  1mod (7)
2n -1  0 mod (7)
Divisible for n=3k
(ii) When n=3k+1
2n = 23k+1  (1)k 2 2mod (7)
2n -1  1 mod (7) ⇒ not divisible
Similarly for n = 3k+2, not divisible
(b) n can be 3k, 3k+1 or 3k+2
 2n  1, 2, 4 mod (7)
2n +1  2, 3, 5 mod (7)
Not divisible for any n.
7. Is it possible for the sum of the first several natural numbers to be 1989?
n ( n + 1)
Sol. = 1989
2
n(n+1) = 3978
3978  3 mod (5)
n (n+1)  0,2,1 mod (5)
not possible
8. Prove that a power of 2 cannot end with four equal digits.
Sol. Put 2n  0 mod (16) for n ≥ 4
NUMBER THEORY 4

Abbbb = 104 a + b (1111)  b (1111) mod (16)

 7b (mod 16)
≠ 0 mod (16) [ b = 2, 4, 6, 8]
9. Jerry has 44 boxes of soda in his truck. The cans of soda in each box are packed oddly so that there
are 113 cans of soda in each box. Jerry plans to pack the sodas into cases of 12 cans to sell. After
making as many complete cases as possible, how many sodas will Jerry have leftover?
Sol. First we not that
44 ≡ 8 (mod 12)
113 ≡ 5 (mod 12)
Thus,
44 . 113 ≡ 8 .5 ≡ 40 ≡ 4 (mod 12)
Meaning there are 4 sodas leftover.
10. If n! denotes the product of the integers 1 through n, what is the remainder when (1!+ 2! + 3! + 4! +
5! + 6!+...) is divided by 9.
Sol. First of all, we know that k! ≡ 0 (mod 9) for all k ≥ 6.
Thus, we only need to find (1! + 2! + 3! + 4! + 5!) (mod 9).
1! ≡ 1 ( mod 9)
2! ≡ 2 ( mod 9)
3! ≡ 6( mod 9)
4! ≡ 24 ≡ 6 (mod 9)
5! ≡ 5. 6 ≡ 30 ≡ 3 ( mod 9)
Thus, (1! + 2! + 3! + 4! + 5!) ≡ 1 + 2 + 6 + 6 + 3 ≡ 18 ≡ 0 (mod 9)
So, the remainder is 0.