Solutions - taught by Joseph Najnudel PDF

Preview

Summary

taught by Joseph Najnudel...

Description

Solutions homework 3 Exercise 1: With the notation of the course, the probability that the number is prime is at least 1 − 4−k log A for A = 1010000 and k = 200. It is 1 − (1/K) where K≥

102440 100040 4200 = 10115. = ≥ 100000 log(1010000 ) 10000 log 10

Exercise 2: 1. We use the fact that



−2 p



=



−1 p

  2 , p

and we check case by case, for each of the 4 possible congruence classes of p modulo 8. 2. If p is congruent to 1 modulo 4, we have     p 3 , = 3 p which is 1 if p ≡ 1 modulo 3, i.e. p ≡ 1 modulo 12, and −1 if p ≡ 2 modulo 3, i.e. p ≡ 5 modulo 12. If p is congruent to 3 modulo 4, we have   p 3 , =− 3 p which is 1 if p ≡ 2 modulo 3, i.e. p ≡ 11 modulo 12, and −1 if p ≡ 1 modulo 3, i.e. p ≡ 7 modulo 12. 3. We have

    5 p , = 5 p

which is 1 if p ≡ 1 modulo 5, and −1 if p ≡ 4 modulo 5. Exercise 3: We have              101 2017 −3 −1 3 101 2 = = = = = = −1 2017 101 101 101 101 3 3 so 101 is not a quadratic residue modulo 2017.                102 2 51 2017 28 7 51 2 = = = = =− =− = −1 2017 2017 2017 51 51 51 7 7 so 102 is not a quadratic residue modulo 2017.                2 −1 −2 103 15 60 2017 103 =1 =− =− =− = = = 15 15 15 15 103 103 103 2017

1

so 103 is a quadratic residue modulo 2017, since 2017 is prime.            26 2 13 2017 2 104 = = = = = −1 2017 2017 2017 2017 13 13 so 104 is not a quadratic residue modulo 2017. Exercise 4: Since p is odd, 2 is invertible in Z/pZ and we can write: 2  5 1 − . x −x−1= x− 2 4 2

If p ≡ 2 or p ≡ 3 modulo 5, we have     p 5 = −1, = 5 p so 5, and then 5/4, is not a square in Z/pZ. Hence, the equation x2 − x − 1 = 0 has no solution. If p = 5, we have 2  1 x2 − x − 1 = x − 2 so the equation has exactly one solution (a ”double root” of x2 − x − 1), which is x = 1/2 = 6/2 = 3. If p is congruent to 1 or 4 modulo 5, we have     p 5 = 1, = 5 p and then there exists δ such that δ 2 = 5 in Z/pZ. We then have      1 2 δ2 1+δ 1−δ − x −x−1= x− = x− x− . 4 2 2 2 2

Since p is prime, Z/pZ is a field and then x2 − x − 1 = 0 if and only if one of the factors just above is equal to 0, which gives two solutions to the equation: (1 + δ)/2 and (1 − δ)/2. The difference between the solutions is δ, which is non-zero modulo p (otherwise δ 2 = 5 = 0 modulo p and then p = 5, but here we assume p congruent to 1 or 4 modulo 5). Hence, we have two distinct solutions to the equation. Exercise 5: 1. We have a(p−1)/2 = 1 since a is a quadratic residue modulo p. Multiplying by a, we deduce that a(p+1)/2 = a. 2. Since p is congruent to 3 modulo 4, (p + 1)/4 is an integer, and the square of a(p+1)/4 is a, i.e. a(p+1)/4 is a square root of a.

2

1

Solutions homework 4

Exercise 1: We have 53 = 1 · 37 + 16, 37 = 2 · 16 + 5, 16 = 3 · 5 + 1, 5 = 5 · 1 + 0. The line of uj in Euclid algorithm gives, from right to left: 1, 0, 1, −3, 7, −10. Hence, we have the Bezout relation 53 · 7 + 37 · (−10) = 1, which gives the particular solution x = 700, y = −1000. Then, the general solution is x = 700 − 37k, y = −1000 + 53k, for k ∈ Z. If we write k = ℓ + 19, we get a parametrization with smaller numbers: x = −3 − 37ℓ, y = 7 + 53ℓ, for ℓ ∈ Z. Exercise 2: 1. A particular solution is (b − 1, −1) and then the general solution is given by (b(1 − k) − 1, ak − 1) for k ∈ Z. If a solution is nonnegative, we need b(1 − k) − 1 ≥ 0, which implies k ≤ 1 − (1/b), and we need ak − 1 ≥ 0, which implies k ≥ 1/a. Since k is an integer, it is not possible to have the two inequalities at the same time. 2. The possible values of u form a periodic set of period b. Hence, the smallest possible nonnegative value of u satisfies 0 ≤ u ≤ b − 1. For this value of u, we get v=

ab − a − b − a(b − 1) c − au > = −1, b b

and then v ≥ 0 since v is an integer. 3. By the first item, ab − a − b cannot be written as au + bv for nonnegative integers u and v , and by the second item, any larger number can be written in this way. Hence, ab − a − b is the largest integer which cannot be written as au + bv for nonnegative integers u and v (notice the typo in the statement of the exercise: you have to replace smallest by largest). Exercise 3: 1. With the notation of the course, we need that d(u2 + v 2 ) = 2016 is divisible by 32, where u and v have different parities, and then u2 + v 2 is odd. Hence, d should be divisible by 32. 2. −1 is not a quadratic residue of 7 because 7 is congruent to 3 modulo 4. Let us assume that u2 + v 2 is divisible by 7. If u is not divisible by 7, and if w is the inverse of u modulo 7, we have (uw)2 + (vw)2 divisible by 7, and then 1 + (vw)2 divisible by 7. This contradicts the fact that −1 is not a quadratic residue of 7. Hence, u is divisible by 7. By symmetry, v is also divisible by 7. 3. We have d(u2 + v 2 ) = 2016 divisible by 7, and u2 + v 2 not divisible by 7, since the coprime integers u and v cannot be both divisible by 7. Hence, d is divisible by 7. 4. We can do the same reasoning with 3 instead of 7, and deduce that u2 + v 2 cannot be divisible by 3 if u and v are coprime. Since d(u2 + v 2 ) = 2016 is divisible by 9, we need that d is divisible by 9.

3

5. From the previous items, d is divisible by 32, 7 and 9, and then divisible by 2016. This contradicts the fact that d(u2 + v 2 ) = 2016. Exercise 4: 1. We have that x2 + z 2 = 2y2 is even, so x and z have the same parity. 2. We deduce that (z − x)/2 and (z + x)/2 are positive integers, such that 

z−x 2

2

+



z+x 2

2

=

z 2 + x2 = y2 . 2

3. There exist d > 0 integer, u > v > 0 coprime integers with different parities, such that z−x z+x = 2duv, y = d(u2 + v 2 ) = d(u2 − v 2 ), 2 2 or

z+x z−x = 2duv, y = d(u2 + v 2 ). = d(u2 − v 2 ), 2 2

Hence, y = d(u2 + v 2 ), z = d(u2 − v 2 + 2uv ), x = εd (u2 − v 2 − 2uv ), where ε ∈ {−1, 1}. Since x ≥ 0, we have x = d|u2 − v 2 − 2uv|.

4

MATH 30200 - number theory Homework set 1, due February 20, 2020 before 4 pm Exercise 1: We have by using Euclid’s algorithm or prime factorization: 92 · 28 gcd(92, 28) = 4, lcm(92, 28) = = 644, 4 and by using prime factorization, gcd(0, 218 · 315 · 511 , −311 · 513 · 711) = 311 · 511 , lcm(0, 218 · 315 · 511, −311 · 513 · 711 ) = 0, gcd(8, 10, 12, 14) = 2, lcm(8, 10, 12, 14) = 23 · 3 · 5 · 7 = 840. Exercise 2: We have 15! = 211 · 36 · 53 · 72 · 11 · 13, and the number of positive divisors of 15! is 12 · 7 · 4 · 3 · 2 · 2 = 4032.

Exercise 3: Using Euclid’s algorithm, we get the Bezout relation: 14 · 9 + 25 · (−5) = 1 and then the inverse of 14 modulo 25 is 9. Similarly, the inverse of 45 modulo 73 is 13. Exercise 4: By looking at the cubes of the integers between −4 and 4 modulo 9, we check that the only possible remainders are 0, 1 or 8, i.e. all cubes are congruent to 0, 1 or −1 modulo 9. The sum of three cubes is then always congruent to an integer between −3 and 3 modulo 9, i.e. it cannot be congruent to 4 or −4 modulo 9. In particular, it cannot be equal to 2020. Exercise 5: If n is divisible by 7, then ϕ(n) is divisible by 6, which contradicts the fact that ϕ(n) = 14. Hence, n cannot be divisible by 7. Since ϕ(n) is divisible by 7, we have pα−1 (p − 1) divisible by 7 for at least one prime power pα involved in the prime factorization of n. Since n is not divisible by 7, p is a prime different from 7, and then 7 divides p − 1. The smallest prime congruent to 1 modulo 7 is 29, hence n should have a prime factor p ≥ 29. But in this case, ϕ(n) is divisible by p − 1 ≥ 28, which contradicts the fact that ϕ(n) = 14. Hence, it is not possible to find n such that ϕ(n) = 14.

1

MATH 30200 - number theory Homework set 2, due March 5, 2020 before 4 pm Exercise 1: We have ϕ(2016) = ϕ(25 · 32 · 7) = (24 · 1)(3 · 2)(6) = 26 · 32 . Removing the factor 7 divides Euler’s function by 6, which can be compensated by a multiplication by 6. Hence, we get: ϕ(26 · 33 ) = ϕ(2016) and then we can take n = 1728. Exercise 2: We have that (Z/2016Z)∗ is isomorphic to (Z/32Z)∗ × (Z/9Z)∗ × (Z/7Z)∗ and then isomorphic to the additive group (Z/8Z) × (Z/2Z) × (Z/6Z) × (Z/6Z), or (Z/8Z) × (Z/2Z)3 × (Z/3Z)2 . We deduce that all elements have order dividing the lcm of 2, 3, 8, which is 24. In the last group, the element (1, 1, 1, 1, 1, 1) has order 24, which is then the largest possible order of an element of (Z/2016Z)∗ Exercise 3: We have (Z/1105Z)∗ isomorphic to (Z/4Z) ×(Z/12Z) ×(Z/16Z) because the prime factorization of 1105 is 5 · 13 · 17. As in the previous exercise, the largest possible order of an element of (Z/1105Z)∗ is also the lcm of all possible orders, which is the lcm of 4, 12, 16, i.e. 48. Since 48 divides 1104, we deduce that x1104 = 1 for all x ∈ (Z/1105Z)∗ , and then 1105 is a Carmicha¨el number. Exercise 4: We have 102018 = 100 × 102016 ≡ 100 [2017]. Since 10 is even and 2018 ≥ 5, we have that 102018 is divisible by 25 , i.e. 102018 ≡ 0 [32]. We have ϕ(63) = ϕ(32 · 7) = 3 · 2 · 6 = 36 and since 2016 is divisible by 36, 102016 ≡ 1 [63] and 102018 ≡ 100 [63]. By Chinese remainder theorem, the congruence class of 102018 modulo 2016 is the congruence class of any number congruent to 0 modulo 32 and 100 modulo 63. We have immediately the Bezout relation: 32 · 2 + 63 · (−1) = 1, and then 64 is congruent to 0 modulo 32 and congruent to 1 modulo 63. Multiplying by 100, we deduce that 6400 is congruent to 0 modulo 32 and to 100 modulo 63, which gives 102018 ≡ 6400 [2016] or 102018 ≡ 352 [2016].

1

2

Exercise 5: We have n = 7 · 13 and then ϕ = 6 · 12 = 72. The inverse of 29 modulo 72 is d = 5. The initial message is the N d = 105 modulo 91, and then 82 modulo 91....