For 13:10, might help to clarify that the expansion of (1 + pz)^p will not have a "p" term because the binomial coefficient of pz will be p making it p^2z at a minimum.
7:42 gcd(x;p) is either 1 or p. If gcd(x;p)=1 then p does not divide x. Letting m=x we get gcd(p,x(1-r^(p-2) +pr^(p-2)) which is either 1 or p. If it is p, then p|x(1-r^(p-2) +pr^(p-2). Since p does not divide x, we must have p|(1-r^(p-2) +pr^(p-2). This means that p|(1-r*(p-2)) which is a contradiction since r is a primitive root mod p, so we have gcd(p,x(1-r^(p-2) +pr^(p-2)) =1. 7:50 If gcd(x,p) = p which means p|x, then letting m=1 we get gcd(p, x+(p-1)r^(p-2)) which is either 1 or p. If it is p, then p|(p-1)r^(p-2) so p|r*(p-2) which means r*(p-2)=pk for some integer k and so r*(p-1)=rpk (a multiple of p) which is a contradiction. Hence gcd(p, x+(p-1)r^(p-2))=1. 9:40 Note that for the order of g mod p^k to exist we must have that p^k does not divide g^d. This is guaranteed as p does not divide r, so p does not divide g. 13:44 Perhaps someone can tell me an easier way to show that gcd(p,z_l) =1, but it seems that a big step was omitted here! Solving g^(p-1)= 1+pz for z gives z=x+(p-1)mr^(p-2) + py for some integer y. Since gcd(p,x+(p-1)mr^(p-2))=1 for appropriate choice of m we have gcd(p,z)=1. g^(p-1)^p^l = (1+pz)^p^l = 1+p^(l+1) z_l. Expanding (1+pz)^p^l and rearranging we get z_l = z + pt for some integer t. Therefore gcd(p,z_l) = 1. 22:08 By Euler, a^ϕ(2^k)=1mod 2^k since a is odd. Suppose a is not a primitive root mod 2^k and d is the order of a mod 2^k, then a^d=1mod 2^k, d
30:30 You say "the fact that k is not prime..." , but k certainly *could* be a prime, correct? I don't think it affects the proof ultimately but it confused me for a several minutes when you said that. Maybe you misspoke and merely wanted to allude to the next step being the prime factorization of k?
The weirdest thing about the p^k case is that the g didn’t depend on k. That means g is a special integer such that for any k, when reducing g mod p^k you always get a primitive root. Is this actually true?
How did you write your comment TWO WEEKS AGO when this video was uploaded just A FEW MINUTES AGO??? 😳 Did you use some sorcery or some kind of interdimensional time travel?
Essentially, convince yourself that g^d=1mod(p^k) implies that g^d=1mod(p), and the the result follows. For further explanation think about this: a=1modp^2 then a=1+(p^2)m => a=1+p(pm) => a=1modp. Applying this above we get g^d=1modp^k implies g^d=1modp, but ord_p(g)=p-1 do p-1|d by previous video.
@@nik5132I like the explanation but it isnt in the correct direction. the way i think about it is that g^(p-1) = 1 (mod p) which means g^k(p-1) = 1 (mod p). Naturally this g^k(p-1) is a bigger number and possibly equal to some p^k+1. note that this isnt exactly a rigorous explanation but it is more of an intuitive explanation for why it makes sense.
This is my guess :g is a primitive root mod p^k (ord(g) modulo p^k is phi(p^k))and also we know that for this case we are not looking for p=2 so by its definition g should be odd and every power of g is 1 modulo 2. Thus d=ord(g) mod p^k because g is always one mod 2. And so d=phi(p^k) and phi(p^k)/d.
@@dragandraganov4384 thanks! Now I got it. G is primitive root modulo p^k und thus phi(p^k) must be a divisor of every power for which g^d = 1 (mod p^k) 👍
Agree that this step is completely unclear. For me the next explanation has worked: because g=r (mod p^k) we can rewrite it as r^d=1(mod p^k). Due to the fact that r is a primitive root, we can set d=phi(p^k).
There are two possibilities. Case 1: gcd(p,x)=1, in this case we take m=0. Case 2 : gcd(p,x)!=1, i.e. p divides x. Here, we take m=1 , i.e., we add a non-multiple of p to a multiple of p. In this case, the gcd of p and the other number turns out to be 1.
It's by construction. Because k is not equal to 1, it must have some prime factor (he writes this, but says something else instead). Let's call this prime factor q and then k = qx for some x. Could it divide d? Doesn't matter, we just needed to pick out one of the factors of k.
Solving g^(p-1)= 1+pz for z gives z=x+(p-1)mr^(p-2) + py for some integer y. Since gcd(p,x+(p-1)mr^(p-2))=1 for appropriate choice of m we have gcd(p,z)=1. g^(p-1)^p^l = (1+pz)^p^l = 1+p^(l+1) z_l. Expanding (1+pz)^p^l and rearranging we get z_l = z + pt for some integer t. Therefore gcd(p,z_l) = 1.
Spoiler alert. For those who want to check their answers to the warm-ups. 4 has primitive root 3 9 has primitive roots 2, 5 10 has primitive roots 3, 7 22 has primitive roots 7, 13, 17, 19 27 has primitive roots 2, 5, 11, 14, 20, 23 31 has primitive roots 3, 11, 12, 13, 17, 21, 22, 24 8, 12, 16, 28, 33 have no primitive roots We know 3 has primitive root 2 because φ(3)=2 and 2^2 ≡ 1 mod 3. And 9 has primitive roots 2, (2+3) = 2, 5. Since 9 has primitive roots 2, 5, then 18 (=2*9) has primitive roots 5 and 2+9 (because 2 is even), giving 5, 11. We know 2 and 3 are primitive roots of 5 because φ(5)=4 and 2^4 = 16 ≡ 1 mod 5, also 3^4 = 81 ≡ 1 mod 5. Then we find that 25 has primitive roots 2, 3, 3+5, 2+10, 3+10, 2+15, 2+20, 3+20 = 2, 3, 8, 12, 13, 17, 22, 23.
Is there any way of knowing without having to do any calculations that 2+5 and 3+15 are not primitive roots of 5^2? I mean, I know there can only be 8 p.r. of 25, so not all r+5k (r being a p.r. of 5) will work since there are 10 such combinations given two values of r and k can range from 0 to 4, so two of the r+5k must not be of order 20.
@@knivesoutcatchdamouse2137 Do you have an answer to this, or do you just have to check them? Also I have a small doubt. Michael said in the video that if r is a primitive root mod p, then r + mp is a possible primitive root (mod p^k) for some k and some m = {0,1}. Does this just mean we are guaranteed a primitive root amongst r and r + p (mod p^k) and we have to still check all residues that are expressible as r + mp mod p^k? Thanks.
This is my solution for the third question: by the difference of squares formula we have: n!=(m!-2)m! . Note that if m>=4 m! is 0 modulo 4 and m!-2 is 2 mod 4 m!-2=(m+1)(m+2)(m+3)…n. If m>3then then n-m
Output from my Python program:- 4 has a primitive root, becos 4 in {1,2,4} 8 has no primitive root, becos 2^2 | 8 and 8 > 4 9 has a primitive root, becos 9 = (prime 3)^2 10 has a primitive root, becos 10 = 2^1 * (prime 5)^1 12 has no primitive root, becos 2^2 | 12 and 12 > 4 16 has no primitive root, becos 2^2 | 16 and 16 > 4 22 has a primitive root, becos 22 = 2^1 * (prime 11)^1 27 has a primitive root, becos 27 = (prime 3)^3 28 has no primitive root, becos 2^2 | 28 and 28 > 4 31 has a primitive root, becos 31 = (prime 31)^1 33 has no primitive root, becos 33 has different odd prime factors Numbers with primitive roots:- [4, 9, 10, 22, 27, 31] Numbers without primitive roots:- [8, 12, 16, 28, 33] phi(9) = 6, ord_9(2) = 6 2 is a primitive root mod 9 phi(18) = 6, ord_18(11) = 6 11 is a primitive root mod 18 phi(25) = 20, ord_25(2) = 20 2 is a primitive root mod 25
More output from my Python program:- List of all primitive roots modulo 9:= [2, 5] List of all primitive roots modulo 18:= [5, 11] List of all primitive roots modulo 25:= [2, 3, 8, 12, 13, 17, 22, 23]
The best theorem which was left unproven in my number theory course, thanks for proving it here
For 13:10, might help to clarify that the expansion of (1 + pz)^p will not have a "p" term because the binomial coefficient of pz will be p making it p^2z at a minimum.
If someone can understand the rest of the video i don't think it's very difficult to see that it's true
yes, the choice of m was purposely made to ensure this.
7:42 gcd(x;p) is either 1 or p. If gcd(x;p)=1 then p does not divide x. Letting m=x we get gcd(p,x(1-r^(p-2) +pr^(p-2)) which is either 1 or p. If it is p, then p|x(1-r^(p-2) +pr^(p-2). Since p does not divide x, we must have p|(1-r^(p-2) +pr^(p-2). This means that p|(1-r*(p-2)) which is a contradiction since r is a primitive root mod p, so we have gcd(p,x(1-r^(p-2) +pr^(p-2)) =1.
7:50 If gcd(x,p) = p which means p|x, then letting m=1 we get gcd(p, x+(p-1)r^(p-2)) which is either 1 or p. If it is p, then p|(p-1)r^(p-2) so p|r*(p-2) which means r*(p-2)=pk for some integer k and
so r*(p-1)=rpk (a multiple of p) which is a contradiction. Hence gcd(p, x+(p-1)r^(p-2))=1.
9:40 Note that for the order of g mod p^k to exist we must have that p^k does not divide g^d. This is guaranteed as p does not divide r, so p does not divide g.
13:44 Perhaps someone can tell me an easier way to show that gcd(p,z_l) =1, but it seems that a big step was omitted here!
Solving g^(p-1)= 1+pz for z gives z=x+(p-1)mr^(p-2) + py for some integer y. Since gcd(p,x+(p-1)mr^(p-2))=1 for appropriate choice of m we have gcd(p,z)=1.
g^(p-1)^p^l = (1+pz)^p^l = 1+p^(l+1) z_l. Expanding (1+pz)^p^l and rearranging we get z_l = z + pt for some integer t. Therefore gcd(p,z_l) = 1.
22:08 By Euler, a^ϕ(2^k)=1mod 2^k since a is odd. Suppose a is not a primitive root mod 2^k and d is the order of a mod 2^k, then a^d=1mod 2^k, d
the best math channel has posted again
30:30 You say "the fact that k is not prime..." , but k certainly *could* be a prime, correct? I don't think it affects the proof ultimately but it confused me for a several minutes when you said that. Maybe you misspoke and merely wanted to allude to the next step being the prime factorization of k?
The weirdest thing about the p^k case is that the g didn’t depend on k. That means g is a special integer such that for any k, when reducing g mod p^k you always get a primitive root. Is this actually true?
27:38 Let’s think about that 🤔
34:12 Homework
34:27 Good Place To Stop
How did you write your comment TWO WEEKS AGO when this video was uploaded just A FEW MINUTES AGO??? 😳 Did you use some sorcery or some kind of interdimensional time travel?
@@titan1235813 Yeah, that’s time travel 😎
@@goodplacetostop2973 HA! I thought it was most probably sorcery 🙃
These are all part of a playlist. If you are psyched, you can check out up to video 20 right now.
@@MichaelPennMath Oh, I see, I thought you guys were some kind of mathemagicians, being able to do all this kind of weird stuff. Phew! 😅
Your videos help me sleep.
At 11:08 , I didn't get why p-1 must divide d.
Essentially, convince yourself that g^d=1mod(p^k) implies that g^d=1mod(p), and the the result follows. For further explanation think about this: a=1modp^2 then a=1+(p^2)m => a=1+p(pm) => a=1modp. Applying this above we get g^d=1modp^k implies g^d=1modp, but ord_p(g)=p-1 do p-1|d by previous video.
@@nik5132I like the explanation but it isnt in the correct direction. the way i think about it is that g^(p-1) = 1 (mod p) which means g^k(p-1) = 1 (mod p). Naturally this g^k(p-1) is a bigger number and possibly equal to some p^k+1. note that this isnt exactly a rigorous explanation but it is more of an intuitive explanation for why it makes sense.
Could someone elaborate 19:00 why phi(p^k) divides d? The other way around is clear to me.
This is my guess :g is a primitive root mod p^k (ord(g) modulo p^k is phi(p^k))and also we know that for this case we are not looking for p=2 so by its definition g should be odd and every power of g is 1 modulo 2. Thus d=ord(g) mod p^k because g is always one mod 2. And so d=phi(p^k) and phi(p^k)/d.
@@dragandraganov4384 thanks! Now I got it. G is primitive root modulo p^k und thus phi(p^k) must be a divisor of every power for which g^d = 1 (mod p^k) 👍
If g^d = 1 (mod p^k) then g^d = 1 (mod p). If d = a(p-1) + b, for 0
Agree that this step is completely unclear. For me the next explanation has worked: because g=r (mod p^k) we can rewrite it as r^d=1(mod p^k). Due to the fact that r is a primitive root, we can set d=phi(p^k).
7:20 why m is equal to 0 or 1 can someone explain
There are two possibilities.
Case 1: gcd(p,x)=1, in this case we take m=0.
Case 2 : gcd(p,x)!=1, i.e. p divides x. Here, we take m=1 , i.e., we add a non-multiple of p to a multiple of p. In this case, the gcd of p and the other number turns out to be 1.
30:41 How do we know that q divides k and not d?
It's by construction. Because k is not equal to 1, it must have some prime factor (he writes this, but says something else instead). Let's call this prime factor q and then k = qx for some x. Could it divide d? Doesn't matter, we just needed to pick out one of the factors of k.
13:50 I couldn't understand why gcd(p,z_i)=1
Solving g^(p-1)= 1+pz for z gives z=x+(p-1)mr^(p-2) + py for some integer y. Since gcd(p,x+(p-1)mr^(p-2))=1 for appropriate choice of m we have gcd(p,z)=1.
g^(p-1)^p^l = (1+pz)^p^l = 1+p^(l+1) z_l. Expanding (1+pz)^p^l and rearranging we get z_l = z + pt for some integer t. Therefore gcd(p,z_l) = 1.
Sir I have stuck help me with this
Find integers a St 0
102^70+1 should be congruent to 99 mod 113
The solution is a = 60
Spoiler alert.
For those who want to check their answers to the warm-ups.
4 has primitive root 3
9 has primitive roots 2, 5
10 has primitive roots 3, 7
22 has primitive roots 7, 13, 17, 19
27 has primitive roots 2, 5, 11, 14, 20, 23
31 has primitive roots 3, 11, 12, 13, 17, 21, 22, 24
8, 12, 16, 28, 33 have no primitive roots
We know 3 has primitive root 2 because φ(3)=2 and 2^2 ≡ 1 mod 3.
And 9 has primitive roots 2, (2+3) = 2, 5.
Since 9 has primitive roots 2, 5, then 18 (=2*9) has primitive roots 5 and 2+9 (because 2 is even), giving 5, 11.
We know 2 and 3 are primitive roots of 5 because φ(5)=4 and 2^4 = 16 ≡ 1 mod 5, also 3^4 = 81 ≡ 1 mod 5.
Then we find that 25 has primitive roots 2, 3, 3+5, 2+10, 3+10, 2+15, 2+20, 3+20 = 2, 3, 8, 12, 13, 17, 22, 23.
Is there any way of knowing without having to do any calculations that 2+5 and 3+15 are not primitive roots of 5^2? I mean, I know there can only be 8 p.r. of 25, so not all r+5k (r being a p.r. of 5) will work since there are 10 such combinations given two values of r and k can range from 0 to 4, so two of the r+5k must not be of order 20.
@@knivesoutcatchdamouse2137 Do you have an answer to this, or do you just have to check them? Also I have a small doubt. Michael said in the video that if r is a primitive root mod p, then r + mp is a possible primitive root (mod p^k) for some k and some m = {0,1}. Does this just mean we are guaranteed a primitive root amongst r and r + p (mod p^k) and we have to still check all residues that are expressible as r + mp mod p^k?
Thanks.
Please sir help me on some number theory questions
find n,k st n^3-5n+10=2^10
X^6=y^5 +24 find x,y values
Find m and m st n! + 1=(m! - 1)^2
This is my solution for the third question: by the difference of squares formula we have: n!=(m!-2)m! . Note that if m>=4 m! is 0 modulo 4 and m!-2 is 2 mod 4
m!-2=(m+1)(m+2)(m+3)…n. If m>3then then n-m
@@dragandraganov4384 thanks
Wrong solution
No solution
Bad solution
Lazy? Why not get your computer to do the homework for you?
[ spoiler alert ]
Output from my Python program:-
4 has a primitive root, becos 4 in {1,2,4}
8 has no primitive root, becos 2^2 | 8 and 8 > 4
9 has a primitive root, becos 9 = (prime 3)^2
10 has a primitive root, becos 10 = 2^1 * (prime 5)^1
12 has no primitive root, becos 2^2 | 12 and 12 > 4
16 has no primitive root, becos 2^2 | 16 and 16 > 4
22 has a primitive root, becos 22 = 2^1 * (prime 11)^1
27 has a primitive root, becos 27 = (prime 3)^3
28 has no primitive root, becos 2^2 | 28 and 28 > 4
31 has a primitive root, becos 31 = (prime 31)^1
33 has no primitive root, becos 33 has different odd prime factors
Numbers with primitive roots:-
[4, 9, 10, 22, 27, 31]
Numbers without primitive roots:-
[8, 12, 16, 28, 33]
phi(9) = 6, ord_9(2) = 6
2 is a primitive root mod 9
phi(18) = 6, ord_18(11) = 6
11 is a primitive root mod 18
phi(25) = 20, ord_25(2) = 20
2 is a primitive root mod 25
More output from my Python program:-
List of all primitive roots modulo 9:=
[2, 5]
List of all primitive roots modulo 18:=
[5, 11]
List of all primitive roots modulo 25:=
[2, 3, 8, 12, 13, 17, 22, 23]