Proof of Fermat's Little Theorem: g Generator of Fp*

Click For Summary
SUMMARY

To prove that g is a generator of Fp* if and only if g^(p-1) = 1 (mod p) and g^q ≠ 1 (mod p) for all prime divisors q of (p – 1), one must apply Fermat's Little Theorem. This theorem states that if p is a prime, then for any integer a not divisible by p, a^(p-1) ≡ 1 (mod p). The discussion emphasizes the necessity of understanding finite fields and their unit groups to effectively apply this theorem in the proof.

PREREQUISITES
  • Understanding of Fermat's Little Theorem
  • Knowledge of finite fields
  • Familiarity with group theory, specifically unit groups
  • Basic modular arithmetic
NEXT STEPS
  • Study the applications of Fermat's Little Theorem in number theory
  • Explore the structure of finite fields and their properties
  • Research the concept of generators in group theory
  • Learn about prime factorization of integers and its implications in modular arithmetic
USEFUL FOR

This discussion is beneficial for mathematicians, cryptographers, and computer scientists interested in number theory, particularly those working with finite fields and modular arithmetic.

jacquelinek
Messages
3
Reaction score
0
Prove that:
g is a generator of Fp* if and only if g^(p-1) = 1 (mod p) and gq ≠ 1 (mod p) for all prime divisors q of (p – 1).

I am thinking about applying Fermat's theorem...but don't know how...
Request help, thanks.
 
Physics news on Phys.org
Should that be gq?

Fermat's theorem may be useful for part of the proof. It certainly cannot prove this theorem all by itself.

What do you know about finite fields? And about their unit groups?
 

Similar threads

Undergrad How to show ##p(x)=g(x)x\pm 1\in\Bbb{Q}[x]## is irreducible in ##\Bbb{Q}_{\Bbb{Z}}[x]##?
  • · Replies 48 ·
2
Replies
48
Views
6K
Undergrad Fundamental theorem of arithmetic from Jordan-Hölder theorem
  • · Replies 5 ·
Replies
5
Views
3K
Undergrad How to Prove a Congruence Relation for Prime Numbers?
  • · Replies 17 ·
Replies
17
Views
2K
Undergrad ##(A/\mathfrak{a})_{\mathfrak{p}/\mathfrak{a}}## and its isomorphism?
  • · Replies 31 ·
2
Replies
31
Views
3K
Undergrad Questions about non existence of GCDs vs (coimages, cokernels)
  • · Replies 12 ·
Replies
12
Views
1K
Undergrad How Do Properties of Modulus Algebra Apply to RSA and Diffie-Hellman?
  • · Replies 12 ·
Replies
12
Views
3K
Graduate Lemma used to prove Von Staudt's Theorem
  • · Replies 1 ·
Replies
1
Views
2K
MHB Fermat's Little Theorem .... Anderson and Feil, Theorem 8.7 .... ....
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Fermat's Little Theorem .... Anderson and Feil, Theorem 8.7 .
  • · Replies 3 ·
Replies
3
Views
3K
Undergrad Trouble understanding an online solution to an exercise in Dummit & Foote
  • · Replies 21 ·
Replies
21
Views
2K