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

  • Context: Graduate 
  • Thread starter Thread starter oszust001
  • Start date Start date
  • Tags Tags
    Proof
Click For Summary

Discussion Overview

The discussion revolves around proving the congruence relation \( a^m \equiv a^{m-\phi(m)} \mod m \). Participants explore the conditions under which this holds, particularly focusing on the relationship between \( a \) and \( m \), and the implications of the Euler's totient function \( \phi(m) \). The scope includes theoretical aspects of number theory and modular arithmetic.

Discussion Character

  • Exploratory
  • Technical explanation
  • Mathematical reasoning

Main Points Raised

  • One participant suggests that the proof requires \( a \) and \( m \) to be relatively prime, citing a counterexample with \( a = 2 \) and \( m = 6 \).
  • Another participant notes that under the assumption of relative primality, the equation can be transformed into \( a^{\phi(m)} \equiv 1 \mod m \), which is a well-known result.
  • A proposed method for proving the result includes proving it for prime numbers using Fermat's Little Theorem, then extending it to powers of primes, and finally using induction on \( m \).
  • There is a mention of the multiplicative properties of \( \phi \) and a condition regarding congruences for relatively prime integers.
  • A later reply raises a question about the applicability of the equation for non-principal numbers, seeking clarification on how to demonstrate its validity in those cases.

Areas of Agreement / Disagreement

Participants generally agree on the necessity of the relative primality condition for the proof, but there is uncertainty regarding the applicability of the equation to non-principal numbers, indicating that multiple views remain on this aspect.

Contextual Notes

The discussion does not resolve the implications of the equation for non-principal numbers, and the assumptions required for the proofs are not fully explored.

oszust001
Messages
10
Reaction score
0
How to proof that equation?
a^m [tex]\equiv[/tex] 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 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
MHB About a variant of the Chinese Remainder Theorem
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Invertible Matrix Proof: A-Transpose * M * A (n by m)
  • · Replies 11 ·
Replies
11
Views
2K
MHB Prove that CnXCm isomorphic to Cgcd(m,n)XClcm(m,n)
  • · Replies 3 ·
Replies
3
Views
3K
Undergrad Proof regarding congruence relation
  • · Replies 4 ·
Replies
4
Views
2K
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
Graduate Anti-dual numbers and what are their properties?
  • · Replies 1 ·
Replies
1
Views
2K