How to Prove a^m ≡ a^{m-φ(m)} mod m?

  • Thread starter Thread starter oszust001
  • Start date Start date
  • Tags Tags
    Proof
Click For Summary
SUMMARY

The discussion focuses on proving the equation a^m ≡ a^{m-φ(m)} mod m, under the condition that a and m are relatively prime. Key insights include the equivalence of this equation to a^{φ(m)} = 1 (mod m), which is established using properties of the Euler's totient function φ. The proof strategy involves three steps: proving for prime numbers using Fermat's Little Theorem, extending the proof to powers of primes, and applying mathematical induction on m. Additionally, understanding the multiplicative properties of φ and the implications of congruences is crucial.

PREREQUISITES
  • Understanding of Euler's totient function (φ)
  • Fermat's Little Theorem
  • Basic principles of modular arithmetic
  • Mathematical induction techniques
NEXT STEPS
  • Study the proof of Fermat's Little Theorem in detail
  • Learn about the multiplicative properties of the Euler's totient function
  • Explore induction proofs in number theory
  • Investigate modular arithmetic applications in cryptography
USEFUL FOR

Mathematicians, number theorists, and students studying modular arithmetic and number theory, particularly those interested in proofs involving the Euler's totient function and congruences.

oszust001
Messages
10
Reaction score
0
How to proof that equation?
a^m \equiv a^{m-\phi(m)} mod m ?
 
Physics news on Phys.org
You need to assume that a and m are relatively prime, right? If not, then a = 2 and m = 6 is a counterexample.

Hint: Do you know any formulas involving congruences and the phi function?
 
By modulo arithmetic this is equivalent to a^{phi(m)}=1 (mod m) where I have assumed that a and m are relatively prime. This result is well-known, but if you want to prove it (and I suggest you to do this) I would suggest that you

1) prove it for primes (fermats little)
2) prove it for powers of primes (use 1) + binomial formula)
3) prove it by induction on m (split up m in relatively prime factors, if its not possible use 2) )

You should be familiar with the multiplicative properties of phi. It is also essential that you know the fact that if x = 1 mod a, x = 1 mod b, then x = 1 mod ab whenever a and b are relatively prime. This is easily verified.

alternatively you could follow the same lines as in the proof of fermats little.
 
Last edited:
Ok but what can I say for nonprincipal numers? how can I show that the equation has sens for every numbers not only for principal
 

Similar threads

Undergrad Proof for subgroup -- How prove it is a subgroup of Z^m?
  • · Replies 11 ·
Replies
11
Views
3K
Undergrad What is the size of the quotient group L/pZ^m?
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Why do the lines m and l coincide in the proof of the parallelogram rule?
  • · Replies 4 ·
Replies
4
Views
3K
MHB Linear Maps in $\mathbb{R}^n$ and $\mathbb{R}^m$: Proving Properties with $M$
  • · Replies 10 ·
Replies
10
Views
2K
Undergrad Invertible Matrix Proof: A-Transpose * M * A (n by m)
  • · Replies 11 ·
Replies
11
Views
2K
Undergrad Proof regarding congruence relation
  • · Replies 4 ·
Replies
4
Views
2K
MHB Prove that CnXCm isomorphic to Cgcd(m,n)XClcm(m,n)
  • · Replies 3 ·
Replies
3
Views
3K
Undergrad Question on Primitive Roots and GCDs
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad How to Prove a Congruence Relation for Prime Numbers?
  • · Replies 17 ·
Replies
17
Views
2K
MHB Is $\phi(U)$ a Subspace of $\mathbb{R}^m$?
  • · Replies 10 ·
Replies
10
Views
2K