Introduction to number theory lecture 24. Primitive roots for prime powers

[@johnchessant3012]

The p-1 method is useful if you're looking at primes of a specific form, like Fermat numbers 2^(2^n)+1 or the Sierpinski problem (k*2^n+1).

[@benjamindavid7371]

At 3:15 The expansion of (g + p)^(p-1) should be g^(p-1) + g^(p-2) p (p-1) + p^2 (...), but since g^(p-2) p (p-1) is not divisible by p^2 it still follows that (g + p)^(p-1) is not congruent to 1 mod p^2.

[@migarsormrapophis2755]

yeeeeeeeee

[@hausdorffm]

4:11 Jacobi symbol (a/b) is defined for any odd numbers a,b. When we prove the statement that Jacobi symbol is the sign of permutation Z/bZ -> Z/bZ; x -> ax in Lecture 35, we use the fact that p^k has a primitive root for any odd prime p. As mentioned at 4:11, 2^3 has NO primitive roots, so I guess, this relates why the Jacobi symbol is considered for odd numbers. 6:55 Typo. left hand sides use n, but right hand side use m. They are same, i.e., m = n. 10:55 Wilson's theorem is the case of m is a prime, so this is the Gauss's extension of Wilson's theorem? 10:55 I do not understand well about the equivalence of 10:55. 12:35 5 is an "almost" primitive root of 2^k. That is, any number coprime to 2^k is either 5^n or -5^n for some n. 14:00 When p = 2, we notice that 5 has order p^{n+1} mod p^{n+3}. I do not know but, if two sets {5^k,k=1,2,...} and { (-5)^k, k= 1,2,...} does not intersect, then their union consists of 2p^{n+1} elements and 2p^{n+1} = p^{n+2} = p^{n+3-1}(p-1) = phi(p^{n+3}) = #Z/2^{n+3}Z. 7:22 Proposition. If g is a primitive root of p^2 for an odd prime number p, then, g is also a primitive root of p^n for any positive integer n. Proof is induction. Let g be a primitive root of p^2, that is g is a primitive root of p or sum of p and a primitive root of p. Prop(n) = { g^{(p-1)p^{n-1}} = 1 + tp^n for some t not divisible by p} If Prop(n) is true, then g is a primitive root of p^{n+1}. The reason why we assume that t is not divisible by p is to deduce g^k is not 1 for any k less than #(Z/(n+1)Z)^*. Now, assume Prop(n), then g^{(p-1)p^{n}} = (1 + tp^n)^p = 1 + ptp^n + p(p-1)/2t^2p^{2n}+.... = 1 + tp^{n+1} + Qp^{2n+1}, for some Q, where we use p is not 2. = 1 + (t + Qp)p^{n+1} = 1 + t' p^{n+1} where t' = t + pQ. Because gcd(t', p) =gcd(t+pQ, p) = gcd(t,p) = 1, we can say that t' is also not divisible by p. Thus, we get Prop(n+1) from Prop(n). Q.E.D. 15:24 ~ Using a primitive root g of prime p, we can consider logarithms of base g as the following isomorphism. log: (Z/pZ)^* -> Z/(p-1)Z; g^n -> n. 19:33 Primality test Let p be a number and suppose we do not know whether or not p is prime. I am not sure, but recall that if there is an element g of (Z/pZ)^* such that the order of g is p-1, then p is prime. So, using this statement, the primality of p is reduced to the existence of g whose order is p-1. We should check that g^q is not congruent to 1 mod p for any factor q dividing p-1. But it is redundant and we do not need to check for all factor. To find such g, it is sufficient to check that g^{(p-1)/q} is not congruent to 1 mod p for any "prime" q dividing p-1. For example, if p = 13, and suppose that we try to check that p = 13 is prime or not. What we have to show is that there is an element of order 12 = p-1. Because any element has order q dividing p-1, to show that g has order p, we have to check g^q is not 1 mod p for any q dividing p-1. If p=13, then p-1 = 12, and hence possible orders is factor of 12, that is, 2, 4, 3, 6. We do not need to check for 2, 4, 3, 6, but it is sufficient to check for only two indicies 12/2 = 6 and 12/3 = 4. Because if g^{12/2} is not 1 mod p, then it automatically follows that g^3, g^2 is also not 1 mod p. If we get some g so that g^q is not 1 for any q which divides p-1, then we may say that g has order p-1, that is, g is primitive root. 15:58 The table of 15:58 describes the map of logarithm, which is defind by log: (Z/pZ)^* -> Z/(p-1)Z; g^n -> n, where g is a primitive root of p. For example, because 1 = 2^4 = 2^0 mod 5, 2 = 2^1 mod 5, 3 = 2^3 mod 5, 4 = 2^2 mod 5, the table of 15:58 of p = 5 is N| 1, 2, 3, 4,