Modulo Arithmetic: Is a^{\varphi(n)}\equiv 1 (mod \;n) for gcd(a,n)=1?

  • Thread starter Thread starter Ted123
  • Start date Start date
  • Tags Tags
    Arithmetic
Click For Summary
SUMMARY

The discussion confirms that if \( A \equiv B \mod{\varphi(N)} \) and \( \gcd(a, N) = 1 \), then \( a^A \equiv a^B \mod{N} \) holds true. This relationship is derived from Euler's theorem, which states that \( a^{\varphi(n)} \equiv 1 \mod{n} \) under the same condition of coprimality. The participants emphasize the importance of understanding this theorem for solving various number theory problems.

PREREQUISITES
  • Understanding of Euler's totient function, \(\varphi(N)\)
  • Knowledge of modular arithmetic
  • Familiarity with the concept of coprimality, specifically \(\gcd(a, N) = 1\)
  • Basic principles of number theory
NEXT STEPS
  • Study Euler's theorem and its applications in number theory
  • Learn about modular exponentiation techniques
  • Explore advanced topics in number theory, such as multiplicative functions
  • Investigate practical applications of modular arithmetic in cryptography
USEFUL FOR

This discussion is beneficial for students of number theory, mathematicians, and anyone interested in the applications of modular arithmetic in cryptography and algorithm design.

Ted123
Messages
428
Reaction score
0
Is it true that if [itex]A \equiv B \mod{\varphi(N)}[/itex] where [itex]\varphi (N)[/itex] is Euler's totient function then [itex]a^A \equiv a^B \mod{N}[/itex]?

I'm not after a proof or anything but I didn't do a number theory course and it seems that this fact is used in many questions I'm currently doing.
 
Physics news on Phys.org
You need to assume gcd(a,N)=1 as well.
 
The more popular format is

[itex]a^{\varphi(n)}\equiv 1 (mod \;n)[/itex] where [itex]gcd(a,n)=1[/itex]
 

Similar threads

U(n) as an External Direct Product
  • · Replies 11 ·
Replies
11
Views
2K
Proving 2 as a Primitive Root of Z_83: A Step-by-Step Approach
  • · Replies 4 ·
Replies
4
Views
2K
Congruence and Primes: Proving the Order of an Integer Modulo a Prime
  • · Replies 4 ·
Replies
4
Views
2K
Can Discrete Logarithms Be Added in Modular Arithmetic?
  • · Replies 16 ·
Replies
16
Views
2K
Euler's Totient Function, Proof
  • · Replies 9 ·
Replies
9
Views
3K
Generalizing the Theorem: Number of Solutions to x^k ≡ 1 (mod n)
  • · Replies 4 ·
Replies
4
Views
3K
High School What theorems are available when using modulo arithmetic?
  • · Replies 11 ·
Replies
11
Views
2K
What Is the Smallest Integer d Such That a^d Equals 1 Mod n?
  • · Replies 2 ·
Replies
2
Views
1K
Prove that ## aa_{1}, aa_{2}, ...., aa_{n} ## is also a complete set?
  • · Replies 14 ·
Replies
14
Views
2K
Finding the orders of 1, 2, .... , 16 (mod 17)
  • · Replies 1 ·
Replies
1
Views
6K