MAT315_Fall_2023_Homework_7_Solutions

University of Toronto Faculty of Arts and Sciences MAT315H1 - F: Introduction to Number Theory Fall 2023 Homework 7 Solutions 1 Problems to be submitted 1. (5 points) In lecture we will prove that there is an infinite number of prime numbers of the forms 7 k +2. Using the same strategy, prove that there are an infinite number of primes of the form 5 k +1 , 5 k +2 , 5 k +3 and 5 k + 4. Hint: You did the character table modulo 5 in homework 6. Solution: For a character χ modulo 5 let us define L ( χ ) := χ (2) 2 + χ (3) 3 + χ (7) 7 + χ (11) 11 + χ (13) 13 + χ (17) 17 + ... We know that when χ is the principal character L ( χ ) = ∞ but that for all other characters L ( χ ) < ∞ . We explain the process we follow for the primes 5 k + 2. For the other cases is analogous and we will just give the answer. Recall that the table of characters modulo 5 is χ 1 χ 2 χ 3 χ 4 1 1 1 1 1 2 1 − 1 i − i 3 1 − 1 − i i 4 1 1 − 1 − 1 We wish to find constants A 2 , A 3 , A 4 so that when we perform L ( χ 1 ) + A 2 L ( χ 2 ) + A 3 L ( χ 3 ) + A 4 L ( χ 4 ) (1) what survives is a constant multiple of 1 2 + 1 7 + 1 17 + 1 37 + ..., that is, the sum of the reciprocals of the primes of the form 5 k + 2. When we sum the fractions whose denominator is the prime p in equation (1) we get 1 + A 2 χ 2 ( p ) + A 3 χ 3 ( p ) + A 4 χ ( p ) p . Hence, what we want is that for p ≡ 1 , 3 , 4 the numerator vanishes and for p ≡ 2 it is nonzero. The equations for the vanishing numerators give a 3 × 3 system: 1 + A 2 + A 3 + A 4 = 0 , 1 − A 2 − iA 3 + iA 4 = 0 , 1 + A 2 − A 3 − A 4 = 0 1

Solving this system we get A 2 = − 1 , A 3 = − i, A 4 = i . We must now verify the numerator for the primes p ≡ 2 does not vanish. We get this numerator is 1 + ( − 1)( − 1) + ( − i )( i ) + ( i )( − i ) = 1 + 1 + 1 + 1 = 4 . We deduce that L ( χ 1 ) − L ( χ 2 ) − iL ( χ 3 ) + iL ( χ 4 ) = 4 2 + 4 7 + 4 17 + 4 37 + ... The left hand side diverges because L ( χ 1 ) = ∞ , while the other three terms converge. Hence, the right hand side must also diverge. Since the terms in the right hand side are the reciprocals of the primes of the form 5 k + 2, we deduce there is an infinite number of them. Following the same procedure we get the following combinations for the other cases L ( χ 1 ) + L ( χ 2 ) + L ( χ 3 ) + L ( χ 4 ) = 4 11 + 4 31 + 4 41 + 4 61 + ... L ( χ 1 ) − L ( χ 2 ) + iL ( χ 3 ) − iL ( χ 4 ) = 4 3 + 4 13 + 4 23 + 4 43 + ... L ( χ 1 ) + L ( χ 2 ) − L ( χ 3 ) − L ( χ 4 ) = 4 19 + 4 29 + 4 59 + 4 79 + ... Remark: Looking at the constants for each case and comparing it with the table of characters we realize that when we want to prove the infinity of primes of the form 5 k + a , the coefficient of L ( χ ) is precisely χ ( a ). This always happens in any situation. This is a manifestation of a property of the character tables that goes by the name Schur Orthogonality Relations and it is one of the most important properties of these objects (the characters). Basically, it is stating that the matrix we have obtained as a character matrix is not any matrix but almost a unitary matrix, i.e. different columns (and different rows) are perpendicular vectors and their Hermitian inner product is zero. (It is not orthogonal because the columns (or rows) are not of norm 1). 2. (a) (3 points) Construct the character table modulo 12. Hint: Use problem 3 of this homework. In lecture we already constructed the tables modulo 3 and modulo 4. (b) (2 points) Prove that there is an infinite number of primes of the form 12 k + 5. Solution: We solve each part separately. Part (a): We have seen in lecture the character tables modulo 3 and 4. Concretely we know the Character Table modulo 3 is X 1 X 2 1 1 1 2 1 − 1 while the one modulo 4 is Y 1 Y 2 1 1 1 3 1 − 1 As matrices they look the same but the characters have different properties and assign values differently. Make sure you do not get confused by this similarity. Page 2

Justify that χ is a Dirichlet Character modulo mn . (b) (3 points) Let χ : Z → C be a Dirichlet Character modulo mn . Prove that there exist a Dirichlet Character ϕ : Z → C modulo m and a Dirichlet Character ψ : Z → C modulo n such that χ is constructed out of ϕ and ψ as in part (a). Hint: To define ϕ at the value a , use the Chinese Remainder Theorem to construct an integer A with A ≡ a (mod n ) and A ≡ 1 (mod m ), and solve for ϕ ( a ). (c) (2 points) Justify that for a given Dirichlet Character χ : Z → C modulo mn , the ϕ and ψ con- structed in the previous part are unique. (d) (2 points) How many different Dirichlet Characters are there modulo 30? Solution: We do part (a) and (d) separately. Parts (b) and (c) we solve at the same time. Part (a): Let ϕ and ψ be a Dirichlet Character modulo m and modulo n , respectively. We claim χ ( k ) := ϕ ( k ) ψ ( k ) is a Dirichlet Character modulo mn . In order for this to be the case, we must verify the three properties of a Dirichlet Character. χ ( k ) = 0 if and only if ( k, mn ) ̸ = 1 : We have that χ ( k ) = 0 if and only if ψ ( k ) ϕ ( k ) = 0, which in turn is equivalent to ϕ ( k ) = 0 or ψ ( k ) = 0. Since ϕ, ψ are Dirichlet characters, we deduce this last condition is equivalent to m | k or n | k . Finally, these two divisibility conditions are equivalent to mn | k (because m, n are relatively prime. Make sure to understand this part). This concludes the first property. Periodicity χ ( k + mn ) = χ ( k ) : Since ϕ is a Dirichlet Character modulo m we have ϕ ( k + mn ) = ϕ ( k ) . Similarly, using that ψ is a Dirichlet Character modulo n ψ ( k + mn ) = ψ ( k ) . Multiplying these two equations we get ϕ ( k + mn ) ψ ( k + mn ) = ϕ ( k ) ψ ( k ) . Thus, using the definition we get χ ( k + mn ) = χ ( k ) . Complete Multiplicativity: Let k, l be integers. We have χ ( kl ) = ϕ ( kl ) ψ ( kl ) = ϕ ( k ) ϕ ( l ) ψ ( k ) ψ ( l ) = ϕ ( k ) ψ ( k ) ϕ ( l ) ψ ( l ) = χ ( l ) χ ( l ) . Notice we have used the complete multiplicativity of ϕ and ψ . In this way, we have a procedure to construct Dirichlet Characters modulo mn out of those modulo m and modulo n . Part (b) and (c): Let us begin with a character modulo mn , say χ . We must construct a character modulo m , that we call ϕ , and one modulo n , that we call ψ , such that χ ( k ) = ϕ ( k ) ψ ( k ) Page 4

For a moment suppose we have constructed such characters. We know all characters modulo N , in any modulus N , satisfy χ ( k ) = 1 if k ≡ 1 (mod N ). Given any congruence class a modulo n , we can construct via the Chinese Remainder Theorem, a unique class modulo mn such that X ≡ 1 (mod m ) , X ≡ a (mod n ) . Say this class modulo mn is C a . Then, from χ ( k ) = ϕ ( k ) ψ ( k ) , we should have when evaluating at C a that χ ( C a ) = ϕ ( C a ) ψ ( C a ) = ϕ (1) ψ ( a ) = ψ ( a ) . That is, we can recover by solving successive systems via the Chinese Remainder Theorem, all the values ψ ( a ). We could do a similar argument to obtain the values of ϕ In conclusion, if χ is a character modulo mn there is at most one possible character modulo m and one character modulo n that satisfy χ ( k ) = ϕ ( k ) ψ ( k ) , and they are defined by the above process, that is, they are defined by the following equations: χ ( C b ) = ψ ( a ) χ ( C a ) = ϕ ( b ) . Notice that C b is defined as the class modulo mn solving X ≡ 1 (mod n ) , X ≡ b (mod m ) . Notice that this uniqueness is what we are required to prove in part (c). What we must prove to conclude part (b), it that the ϕ and ψ defined in this way satisfy the three properties of a Dirichlet Character. We will do it only for ϕ since for ψ is completely analogous. ϕ ( k ) = 0 if and only if m | k : The value of ϕ of the integers with m | k is recovered by solving the system X ≡ 1 (mod n ) , X ≡ 0 (mod m ) . If C 0 represents this class modulo mn (or any integer representing this class) we of course have ( C 0 , mn ) ̸ = 1. Thus, ϕ ( k ) = ϕ ( C 0 ) = 0 , since χ is a Dirichlet Character modulo mn . Periodicity ϕ ( k + m ) = ϕ ( k ) : k and k + m represent the same class modulo m . Hence, their value is represented by the same system X ≡ 1 (mod n ) , X ≡ b (mod m ) . where b is their common congruence modulo m . Thus, ϕ ( k ) = χ ( C b ) = ϕ ( k + m ) . Page 5

Remark: This is a particular case of the properties we mentioned in class that the rows and columns of the table of characters have to satisfy. Solution: We do each part separately. Part (a): There are three properties that must be satisfied for χ 1 to be a Dirichlet Character modulo p . We verify each of them consecutively: χ 1 ( n ) = 0 if and only if p | n : By definition we have that if p | m , then χ 1 ( m ) = 0. Otherwise, its value is ω k p ̸ = 0 for all k . We conclude the character is zero if and only if p | m . Periodicity, χ 1 ( n + p ) = χ 1 ( n ) : Notice that p | n if and only if p | n + p , so that both sides of χ 1 ( n + p ) = χ 1 ( n ) , are zero simultaneously or nonzero simultaneously. If they are zero then there is nothing to prove. Hence, let us suppose p does not divide n and we must prove the above equation holds. This follows from the following: if n ≡ g k (mod p ) then n + p ≡ n ≡ g k (mod p ). Thus χ 1 ( n + p ) = ω k p = χ 1 ( n ) . This proves the periodicity. Complete multiplicativity: For each n that is not divisible by p write n ≡ g k n (mod p ) , for k n an integer in 1 , 2 , ..., p − 1. Notice that for any two integers that are relatively prime to p we have nm ≡ g k n g k m ≡ g k m + k m (mod p ) , but also nm ≡ g k nm (mod p ) . We deduce g k m + k n ≡ g k nm (mod p ) , which implies by the definition of order (and the fact that g is a primitive root) that k m + k n ≡ k mn (mod p − 1) This means that k m + k n = k mn + h ( p − 1) for some integer h . Thus χ 1 ( m ) χ 1 ( n ) = ω k m p ω k n p = ω k m + k m p = ω k mn + h ( p − 1) p = ω k mn p ω h ( p − 1) p = ω k mn p = χ 1 ( mn ) . This proves complete multiplicativity. Notice we used that ω p − 1 p = 1 in the second to lat equality. This concludes (a). Part (b): Let χ be some other Dirichlet Character. Since g p − 1 ≡ 1 (mod p ) we have 1 = χ (1) = χ ( g p − 1 ) = χ ( g ) p − 1 . Page 7

We conclude χ ( g ) is a p − 1 root of unity. We have seen in problem 1 part (b) that all the roots of unity are of the form ω t p for some integer 0 ≤ t ≤ p − 2. Thus, there exists an integer t sch that χ ( g ) = ω t p . If n is any integer relatively prime to p , then we can write (just as in the previous part) n ≡ g k n (mod p ) for some integer k n . Then χ ( n ) = χ ( g k n ) = χ ( g ) k n = ( ω t p ) k n = ( ω k n p ) t = χ 1 ( n ) t . Furthermore, the equality χ ( n ) = χ 1 ( n ) t , holds if p | n since both sides are zero. We conclude that the above equality holds for all integers n , that is, χ = χ t 1 , as desired. Notice the as part of the solutions of this part we have concluded the integer t can be taken to be one of 0 , 1 , ..., p − 2). Part (c): For each integer 0 ≤ k ≤ p − 1 we can define the function χ = χ t 1 . By part (b), we know all the Dirichlet Characters modulo p are of these form. We now justify that all of the functions obtained in these way are Dirichlet Characters modulo p and that they are all different. The properties of a Dirichlet Character are immediate from those of χ 1 . The first property follows from the following: χ ( n ) = 0 if and only if χ 1 ( n ) t = 0 if and only if χ 1 ( n ) = 0 if and only if p | n . Complete multiplicativity follows from χ ( nm ) = χ 1 ( nm ) t = χ 1 ( n ) t χ 1 ( m ) t = χ ( n ) χ ( m ) . Finally, periodicity is χ ( n + p ) = χ 1 ( n + p ) t = χ 1 ( n ) t = χ ( n ) . We conclude all of these functions for t = 0 , 1 , ..., p − 2 are Dirichlet Characters. They are all different since at g they are χ t ( g ) = χ 1 ( g ) t = ω t p , and we have seen in problem 1 that 1 , ω p , ..., ω p − 2 p are all the different ( p − 1)-roots of unity. Thus, because its value at g is different, all of these characters are distinct. Part (d): We begin with a general claim. Let z be an n − th root of unity that is a primitive m -root of unity for some 1 ≤ m ≤ n . Claim 1: m | n : Suppose that is not the case and write, using the Euclidean Algorithm, n = mq + r , where 0 ≤ r < m . Then we have 1 = z n = z mq + r = ( z m ) q z r = z r . We deduce that z r = 1. Since z is a primitive m − th root of unity, we cannot have r being positive for we would contradict that m is the minimal positive exponent for which z m = 1. Thus r = 0 and we have n = mq , that is, m | n . ■ Claim 2: If χ ( a ) = 1 for all characters then a ≡ 1 (mod p ). Clearly if χ ( a ) = 1 then p cannot divide a . Hence, we are free to assume ( p, a ) = 1 and justify the result for these integers. We will see that already χ 1 only takes th value 1 if a ≡ 1 (mod p ). Indeed if a ≡ g k (mod p ) we have χ 1 ( a ) = χ ( g k ) = ω k p . Page 8

We dont write χ (0) since its value is zero and is the only one that vanishes. Let us multiply S by χ ( a ). We get: χ ( a ) S = χ ( a )( χ (1) + ... + χ ( p − 1)) = χ ( a ) χ (1) + ... + χ ( a ) χ ( p − 1) = χ ( a ) + χ (2 a ) + ... + χ (( p − 1) a ) = χ (1) + χ (2) + ...χ ( p − 1) = S. Notice that we have used the complete multiplicativity in the second equality. Furthermore, we have used that a, 2 a, ..., ( p − 1) a is again a reduced residue system. Hence, the sum of the character evaluated over 1 , 2 , ..., p − 1 or over a, 2 a, ..., ( p − 1) a is the same, since each is going over a sum of the character on a reduced residue system. We deduce χ ( a ) S = S, that is, S (1 − χ ( a )) = 0 . Because we have picked χ ( a ) ̸ = 1, we can cancel the term χ ( a ) − 1 ̸ = 0. We thus deduce χ (1) + ... + χ ( p − 1) = 0 . If instead, χ is the principal character, we have that χ (1) + ... + χ ( p − 1) = 1 + · · · + 1 = p − 1 . Remark: This trick of changing the index and obtaining again the same value times some constant is very useful and common when evaluating sums. We will find it again when we study sums of triple products of quadratic symbols. Part (f): Let χ 1 be the character constructed in part (a). In parts (b) and (c) we have seen that all other characters modulo p are χ t := χ t 1 . For any one of these characters, say χ i , define L ( χ i ) = χ i (2) 2 + χ i (3) 3 + χ i (5) 5 + χ i (7) 7 + χ i (11) 11 + χ i (13) 13 + χ i (17) 17 + ... Notice that in the above sum the term corresponding to the prime p does not appear. We know that when i = 0, i.e. for the Principal character modulo p , the above series diverges. In all other cases it is convergent. Let us consider the sum of the series L ( χ 0 ) + L ( χ 1 ) + · · · + L ( χ p − 2 ) . When we collect and add the fractions whose denominator is a given prime q , we obtain a fractions whose numerator is χ 0 ( q ) + χ 1 ( q ) + · · · + χ p − 2 ( q ) . By problem (d) we get this sum is 0 unless q ≡ 1 (mod p ). For q ≡ 1, the sum is p − 1. We conclude L ( χ 0 ) + L ( χ 1 ) + · · · + L ( χ p − 2 ) = ( p − 1)   X q ≡ 1 (mod p ) 1 q   . The left hand side diverges because of the term L ( χ 0 ), as all the others are convergent so they cannot cancel the divergence of L ( χ 0 ). Thus, the right hand side must diverge too. The sum in the right hand side is over the reciprocals of the primes q ≡ 1 (mod p ). We conclude there are an infinite number of primes with q ≡ 1 (mod p ), for otherwise the sum would be finite, and thus convergent. This concludes the problem. Page 10