If I'm not mistaken, this same argument that (Z/pZ)* is cyclic also works to prove the more general theorem that any finite subgroup of F* is cyclic for any field F.
A natural number m has a primitive root "a", iff (Z/mZ)^* is a cyclic group with generator "a". If m has a primitive root g, then there is an isomorphism 12:59 Z/kZ -> (Z/mZ)^*; x -> a^x, where k = phi(m) is the order of (Z/mZ)^*, i.e., phi(m) = | (Z/mZ)^* | Under the isomorphism, the equation 2X = 0 in Z/kZ corresponds to X^2 = 1 in (Z/mZ)^*. If k is even, then 2X = 0 has two solutions 0 and k/2 and thus X^2 = 1 has also two solutions g^0 and g^(k/2). If k is odd , then 2X = 0 has one solution 0 thus X^2 = 1 has also one solutions g^0. Thus, we get the following proposition. Proposition. The equation X^2 = 1 has at most two solutions in (Z/mZ)^*, if m has primitive roots. Corollary. If X^2 = 1 has at least 4 solutions in (Z/mZ)^*, then m has no primitive roots. Corollary. 13:48 If m, n >= 3, then mn has no primitive roots. Proof. Applying Chinese remainder theorem, (Z/mnZ)^* is the product group of (Z/mZ)^* and (Z/nZ)^*, both of them has at least two solutions of the equation X^2 = 1. Thus, (Z/mnZ)^* has at least four solutions of the equation X^2 = 1, which contradicts that mn has primitive roots. Q.E.D. In the proof, we implicitly use the fact that phi(m) and phi(n) are both even. This is because if a < n and gcd(a,n) = 1, then gcd(a, n-a ) = 1. In fact, if there is some x, y so that xa+yn = 1 then (x+y)a + y(n-a) =1. Thus if a and n are coprime, then n-a and n is also coprime. For example, phi(12) = |Z/12Z| = #{1,5,7,11} = #{1,5, 7 = 12-5, 11=12-1} = #{1,12-5} + #{5,12-5} = 2 + 2 = 4. From the Corollary, the possible form of numbers having primitive roots is restricted to one of the forms of 16:25. Problem : Does (Z/pZ)^* have primitive root? -> Yes by Euler. Proved as an application of the fact that zeros of a polynomial of degree n has at most n roots in Z/pZ, where p is prime. For non prime number m, it is false. x^2 -1 = 0 has four roots in Z/8Z. Proof. Induction. Prop(n) := degree n polynomial has at most n roots. Suppose that we get a root, say a, of degree n polynomial f(x) = 0, Then another root c of f(x) is either c = a mod p or a root of lower degree polynomial. Because a is a root of f(x), f(x) = (x-a)g(x) mod p, where degree of g is less than that of f(x). So, f(c) = (c-a)g(c) implies that c = a mod p or g(c) = 0 mod p. So, if g(c) = 0 mod p, then, by the induction, such a solution is at most degree g. Q.E.D. 24:00 (1) In (Z/pZ)^*, the solution of the equation x^n = 1 is at most n solutions. (2) In (Z/pZ)^*, Either there are phi(n) solutions of order n for the equation x^n = 1 or none at all. Because if x is an order n solution of x^n=1, then x^i, gcd(i,n) = 1 is also a solution of order n. So, there are phi(n) solutions of order n. 30:28 About the table of the book "An introduction to the theory of numbers" by Vinogradov. Left table means the number z such that 2^z = 10x+y mod 37 for x-th row and y-th column. Right table means the number z such that z = 2^{10x+y} mod 37 for x-th row and y-th column. 28:27 Problem. Solve x^3 = 1 mod 97. If 97 has a primitive root g, then there are an isomorphism Z/96Z --> (Z/97Z)^*; n --> g^n, where we use 96 = phi(97). This isomorphism translate the equation x^3 = 1 in (Z/97Z)^* to the equation 3k = 0 mod 96. From the equation 3k= 0 mod 96, we get k = 0, 96/3, 2*96/3 = 0, 32, 64 mod 96. By the table of Vinogradov, we notice g = 5. Thus, the solutions of x^3 = 1 mod 97 are g^0, g^32, g^64, which are g^0 = 1, g^32 = 35, g^64 = 61 in (Z/97Z)~* by the Vinogradov table. 31:00 ~ camera is ...
I find math terms are quite confusing. Here we say we have primitive 8th root of unity just by choosing coprime numbers. But we do not have primitive root of mod 8 because x^2 = 1 mod 8 have 4 solutions.
The claim that Euler made a mistake in proving the existence of primitive roots seems rather suspect to me, as the main lemma--- that a polynomial has at most n roots in Z/pZ--- is his, and he understood that this proves existence of primitive roots. Is this actually true that he made a mistake, or is this a case of future generations not understanding what he was saying? Once this lemma is granted, the remainder of the proof follows by relatively simple considerations all available to Euler.
This is a tricky question, whose answer is unclear to me. On the one hand Gauss states (in disquisitiones arithmeticae section 56) that Euler's proof of the existence of primitive roots is incomplete at two points. On the other hand Andre Weil (Number theory, pages 199-200) disagrees with Gauss and says that Euler's proof is essentially correct. Take your pick.
If I'm not mistaken, this same argument that (Z/pZ)* is cyclic also works to prove the more general theorem that any finite subgroup of F* is cyclic for any field F.
At 16:00, how can 2^{k/2} and -2^{k/2} be solutions if their square is 2^k = 0?
Did you mean 2^{k-1}+1 and -2^{k-1}+1?
Yes, I go confused.
Sir, which book you are referring???? For number theory
Why, at 13:00, is it at least 4 (not 3) elements for it not to have a primitive root?
Ah, is it because they come in pairs (x)^2 = (-x)^2 = 1?
in the english language , what is the difference between "a divides b " and "a dividing b" ?
oh , i get it . is it because following by "of" has to change the verb form , so it's a grammar thing .
A natural number m has a primitive root "a", iff (Z/mZ)^* is a cyclic group with generator "a".
If m has a primitive root g, then there is an isomorphism 12:59 Z/kZ -> (Z/mZ)^*; x -> a^x,
where k = phi(m) is the order of (Z/mZ)^*, i.e., phi(m) = | (Z/mZ)^* |
Under the isomorphism, the equation 2X = 0 in Z/kZ corresponds to X^2 = 1 in (Z/mZ)^*.
If k is even, then 2X = 0 has two solutions 0 and k/2 and thus X^2 = 1 has also two solutions g^0 and g^(k/2).
If k is odd , then 2X = 0 has one solution 0 thus X^2 = 1 has also one solutions g^0.
Thus, we get the following proposition.
Proposition. The equation X^2 = 1 has at most two solutions in (Z/mZ)^*, if m has primitive roots.
Corollary. If X^2 = 1 has at least 4 solutions in (Z/mZ)^*, then m has no primitive roots.
Corollary. 13:48 If m, n >= 3, then mn has no primitive roots.
Proof. Applying Chinese remainder theorem, (Z/mnZ)^* is the product group of (Z/mZ)^* and (Z/nZ)^*, both of them has at least two solutions of the equation X^2 = 1.
Thus, (Z/mnZ)^* has at least four solutions of the equation X^2 = 1, which contradicts that mn has primitive roots. Q.E.D.
In the proof, we implicitly use the fact that phi(m) and phi(n) are both even.
This is because if a < n and gcd(a,n) = 1, then gcd(a, n-a ) = 1.
In fact, if there is some x, y so that xa+yn = 1 then (x+y)a + y(n-a) =1.
Thus if a and n are coprime, then n-a and n is also coprime.
For example, phi(12) = |Z/12Z| = #{1,5,7,11} = #{1,5, 7 = 12-5, 11=12-1} = #{1,12-5} + #{5,12-5} = 2 + 2 = 4.
From the Corollary, the possible form of numbers having primitive roots is restricted to one of the forms of 16:25.
Problem : Does (Z/pZ)^* have primitive root? -> Yes by Euler.
Proved as an application of the fact that zeros of a polynomial of
degree n has at most n roots in Z/pZ, where p is prime.
For non prime number m, it is false.
x^2 -1 = 0 has four roots in Z/8Z.
Proof. Induction. Prop(n) := degree n polynomial has at most n roots.
Suppose that we get a root, say a, of degree n polynomial f(x) = 0,
Then another root c of f(x) is either c = a mod p or a root of lower degree polynomial.
Because a is a root of f(x), f(x) = (x-a)g(x) mod p, where degree of g is less than that of f(x).
So, f(c) = (c-a)g(c) implies that c = a mod p or g(c) = 0 mod p.
So, if g(c) = 0 mod p, then, by the induction, such a solution is at most degree g. Q.E.D.
24:00
(1) In (Z/pZ)^*, the solution of the equation x^n = 1 is at most n solutions.
(2) In (Z/pZ)^*, Either there are phi(n) solutions of order n for the equation x^n = 1 or none at all. Because if x is an order n solution of x^n=1, then x^i, gcd(i,n) = 1 is
also a solution of order n. So, there are phi(n) solutions of order n.
30:28 About the table of the book "An introduction to the theory of numbers" by Vinogradov.
Left table means the number z such that 2^z = 10x+y mod 37 for x-th row and y-th column.
Right table means the number z such that z = 2^{10x+y} mod 37 for x-th row and y-th column.
28:27 Problem. Solve x^3 = 1 mod 97.
If 97 has a primitive root g, then there are an isomorphism Z/96Z --> (Z/97Z)^*; n --> g^n, where we use 96 = phi(97).
This isomorphism translate the equation x^3 = 1 in (Z/97Z)^* to the equation 3k = 0 mod 96.
From the equation 3k= 0 mod 96, we get k = 0, 96/3, 2*96/3 = 0, 32, 64 mod 96.
By the table of Vinogradov, we notice g = 5. Thus, the solutions of x^3 = 1 mod 97 are g^0, g^32, g^64,
which are g^0 = 1, g^32 = 35, g^64 = 61 in (Z/97Z)~* by the Vinogradov table.
31:00 ~ camera is ...
I find math terms are quite confusing. Here we say we have primitive 8th root of unity just by choosing coprime numbers. But we do not have primitive root of mod 8 because x^2 = 1 mod 8 have 4 solutions.
The claim that Euler made a mistake in proving the existence of primitive roots seems rather suspect to me, as the main lemma--- that a polynomial has at most n roots in Z/pZ--- is his, and he understood that this proves existence of primitive roots. Is this actually true that he made a mistake, or is this a case of future generations not understanding what he was saying? Once this lemma is granted, the remainder of the proof follows by relatively simple considerations all available to Euler.
This is a tricky question, whose answer is unclear to me. On the one hand Gauss states (in disquisitiones arithmeticae section 56) that Euler's proof of the existence of primitive roots is incomplete at two points. On the other hand Andre Weil (Number theory, pages 199-200) disagrees with Gauss and says that Euler's proof is essentially correct. Take your pick.
ye