Primitive Roots -- Number theory 17

Показать описание

If you are going to use an ad-blocker, considering using brave and tipping me BAT!

Books I like:

Abstract Algebra:

Differential Forms:

Number Theory:

Analysis:

Calculus:

My Filming Equipment:

Рекомендации по теме

Комментарии

The best theorem which was left unproven in my number theory course, thanks for proving it here

jplikesmaths

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.

SanketAlekar

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<ϕ(2^k) and d|ϕ(2^k). ϕ(2^k) = 2^(k-1), so d = 2^l where l < k-1. ϕ(2^k)/2 = 2^(k-2) where l<=k-2, hence d|ϕ(2^k)/2 and so a^(ϕ(2^k)/2)=1 mod 2^k.

eamon_concannon

the best math channel has posted again

yuseifudo

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?

JM-usfr

27:38 Let’s think about that 🤔
34:12 Homework
34:27 Good Place To Stop

goodplacetostop

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?

knivesoutcatchdamouse

At 11:08, I didn't get why p-1 must divide d.

Harsimran_Singh_

Could someone elaborate 19:00 why phi(p^k) divides d? The other way around is clear to me.

thomashoffmann

30:41 How do we know that q divides k and not d?

yusufevrengul

7:20 why m is equal to 0 or 1 can someone explain

yusufevrengul

13:50 I couldn't understand why gcd(p, z_i)=1

yusufevrengul

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.

RexxSchneider

Sir I have stuck help me with this
Find integers a St 0<= a <113
102^70 + 1 is congruent to a^37(mod113)

elvistheawesome

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

elvistheawesome

Lazy? Why not get your computer to do the homework for you?

[ spoiler alert ]

schrodingerbracat

Primitive Roots -- Number theory 17

Number Theory | Primitive Roots modulo n: Definition and Examples

Primitive Roots

Number Theory | Primitive roots of 54

Easy method to find primitive root of prime number

Number Theory | Number of Primitive Roots modulo n

How to Find Primitive Root of a Number | Prime Number | Number Theory | Cryptography

Order of Integers and Primitive Roots

PRIMITIVE ROOTS {NUMBER THEORY} | How to find primitive roots | primitive roots with examples

Number Theory | A primitive root for 2*5^n

Number Theory: Primitive Roots - Oxford Mathematics 2nd Year Student Lecture

Primitive Roots and Indices- Lecture 1

Proof: Every Prime has a Primitive Root

Number Theory: Order of Integers & Primitive Prime Roots

Exercises of Primitive Roots & Indices (part -1) | Lec 28 | Number Theory | Urdu,Hindi

Primitive Roots & Indices - Lecture 10

Number Theory | All primitive roots modulo 22

Applications of primitive roots -- Number Theory 19

Finding primitive root

Primes and Primitive Sets (an Erdős Conjecture is cracked) - Numberphile

AKPotW: Primitive Root and -1 [Number Theory]

How to test if g is a primitive root of a prime number p?

Number Theory | There is a primitive root modulo every power of an odd prime!!

primitive roots of 47 (Number Theory)

primitive roots in number theory csir net maths