Show that a 37 - a is divisible by 1729 for any integer a :

First, 1729 = 7 × 13 × 19. Let b = a 37 - a . We will show that 7 | b , 13 | b , and 19 | b .

Then, since gcd (7 , 13) = 1, 7 | b and 13 | b together imply that 7 × 13 | b

Similarly, since gcd (7 × 13 , 19) = 1, 7 × 13 | b and 19 | b together imply that 7 × 13 × 19 = 1729 | b

Thus, it remains only to show that 7 | b , 13 | b , and 19 | b : ( i ) 7 | b : b = a 37 - a = a ( a 36 - 1) = a ( a 12 - 1)( a 24 + a 12 + 1) = a ( a 6 - 1)( a 6 + 1)( a 24 + a 12 + 1) = ( a 7 - a ) k for some integer k

By Fermat’s little theorem, 7 | a 7 - a for any integer a . Thus 7 | b . ( ii ) 13 | b : 5

As we saw above, b = a ( a 12 - 1)( a 24 + a 12 + 1) = ( a 13 - a )( a 24 + a 12 + 1). By Fermat’s little theorem, 13 | a 13 - a for any integer a , so that 13 | b . ( iii ) 19 | b : b = a 37 - a = a ( a 36 - 1) = a ( a 18 - 1)( a 18 + 1) = ( a 19 - a )( a 18 + 1) By Fermat’s little theorem, 19 | a 19 - a for any integer a , so 19 | b . Thus, by the argument given above, 1729 | a 37 - a for any integer a . 11. Find the smallest non-negative remainder when 3 99 is divided by 5. We know that 3 2 = 9 ≡ ( - 1) mod 5. Then, by theorem 2 ( iv ), page 61, 3 98 ≡ (3 2 ) 49 ≡ ( - 1) 49 mod 5 ≡ - 1 mod 5. So 3 99 ≡ 3 · 3 98 ≡ 3 · ( - 1) ≡ - 3 ≡ 2 mod 5. So, the smallest non-negative remainder when 3 99 is divides by 5 is 2. 12. Find the smallest non-negative remainder when 2 510 is divided by 511. First, 2 9 = 512 ≡ 1 mod 511. So, since 510 = 9(56) + 6, 2 510 ≡ (2 9 ) 56 · 2 6 ≡ 2 6 ≡ 64 mod 511, so the smallest non-negative remainder when 2 510 is divided by 511 is 64. 13. Find the smallest non-negative remainder when 30 30 is divided by 7. First 30 ≡ 2 mod 7, so 30 30 ≡ 2 30 mod 7. Next, 2 3 ≡ 1 mod 7, so 2 30 ≡ (2 3 ) 10 ≡ 1 10 ≡ 1 mod 7. Thus 1 is the smallest non-negative remainder when 30 30 is divided by 7. 14. (2.1.1) List seven members of each of the following congruence classes: ( i ) [13] 9 : 4, 13, 22, 31, 40, -5, -14, etc. 6