Download E-books Number Theory: Structures, Examples, and Problems PDF

B1 b0 , then so does the illustration of x p . n challenge 7. 1. 15. ensure all integers n > 1 such that 2 n+1 is an integer. 2 (31st overseas Mathematical Olympiad) challenge 7. 1. sixteen. end up that for any n > 1 we won't have n | 2n−1 + 1. (Sierpi´nski) challenge 7. 1. 17. turn out that for any typical quantity n, n! is a divisor of n−1 (2n − 2k ). k=0 7. 2 Euler’s Theorem Theorem 7. 2. 1. (Euler’s theorem) permit a and n be quite leading confident integers. Then a ϕ(n) ≡ 1 (mod n). evidence. examine the set S = {a1 , a2 , . . . , aϕ(n) } such as all optimistic integers under n which are quite top to n. simply because gcd(a, n) = 1, it follows that aa1 , aa2 , . . . , aaϕ(n) is a permutation of a1 , a2 , . . . , aϕ(n) . Then (aa1 )(aa2 ) · · · (aaϕ(n) ) ≡ a1 a2 · · · aϕ(n) (mod n). utilizing that gcd(ak , n) = 1, okay = 1, 2, . . . , ϕ(n), the belief now follows. 136 I basics, 7. extra on Divisibility comment. Euler’s theorem additionally follows from Fermat’s little theorem. certainly, enable n = p1α1 · · · pkαk be the best factorization of n. we have now a pi −1 ≡ 1 (mod pi ); αi −1 ( pi −1) accordingly a pi ( p1 −1) ≡ 1 (mod pi2 ), a pi ( pi −1) ≡ 1 (mod pi3 ), . . . , a pi 2 αi ≡1 (mod piαi ). that's, a ϕ( pi ) ≡ 1 (mod piαi ), i = 1, . . . , okay. utilizing this estate to every top issue, the belief follows. challenge 7. 2. 1. turn out that for any confident integer s, there's a confident integer n whose sum of digits is s and s | n. (Sierpi´nski) resolution. If gcd(s, 10) = 1 then enable n = 10sϕ(s) + 10(s−1)ϕ(s) + · · · + 10ϕ(s) . it truly is transparent that the sum of digits of n is s and that n = (10sϕ(s) − 1) + (10(s−1)ϕ(s) − 1) + · · · + (10ϕ(s) − 1) + s is divisible through s, by way of Euler’s theorem. If gcd(s, 10) > 1, then allow s = 2a 5b t with gcd(t, 10) = 1 and take n = a+b 10 (10sϕ(t) + 10(s−1)ϕ(t) + · · · + 10ϕ(t) ). comment. The integers divisible by way of the sum of its digits are referred to as Niven numbers. For a few information regarding those numbers see the comment after challenge four. 2. 12. challenge 7. 2. 2. allow n > three be a wierd integer with major factorization n = α p1α1 · · · pk ok (each pi is prime). If m =n 1− 1 p1 1− 1 p2 ··· 1 − 1 pk , end up that there's a leading p such that p divides 2m − 1, yet doesn't divide m. (1995 Iranian Mathematical Olympiad) resolution. simply because m = ϕ(n) is Euler’s phi functionality and n is strange, we all know via Euler’s theorem that n divides 2m − 1. We ponder circumstances. First permit n = pr > three for a few atypical leading p. Then m = pr − pr −1 is even and m ≥ four. on account that p divides 2m − 1 = (2m/2 − 1)(2m/2 + 1), is also needs to divide one of many elements at the correct. Any leading divisor of the opposite issue (note that this issue exceeds 1) also will divide 2m − 1 yet won't divide n = pr . If n has a minimum of distinctive major elements, then m ≡ zero (mod four) and p − 1 divides m/2 for every major issue of n. for this reason, by means of Fermat’s theorem, p additionally divides 2m/2 − 1. It follows that no major issue of n divides 2m/2 + 1. accordingly any leading issue of 2m/2 + 1 is an element of 2m − 1 yet no longer an element of n. 7. 2. Euler’s Theorem 137 challenge 7. 2. three. allow a > 1 be an integer.