Modulus: 2

Enter a modulus:
Fermat's little theorem:
xp-1 ≡ 1 (mod p)
Modulus is a prime: p = 2
x1 ≡ 1 (mod 2)
Congruence:
Given two integer values a and b
if a ≡ b (mod 2) then a and b are congruent
a - b ≡ 0 (mod 2)

Modulus: 2

Enter a value a:

Calculator: Modulus = 2


Modulus: 2

Euler's Totient Function φ(n)
Euler's totient function calculates the number of positive integers less than n that are coprime with n.
If x and n are coprime, xφ(n) ≡ 1 (mod n)
Calculating φ(n)
φ(p) = p - 1 if p is prime
If n is not prime, express n as a product of prime factors
n = p1k1p2k2... pnkn
φ(n) = (p1-1)p1k1-1 (p1-1)p2k2-1... (pn-1)pnk1-1
Calculation of φ(2)
2 is prime
φ(2) = 2 - 1 = 1
Euler's Theorem
xφ(n) ≡ 1 (mod n) if x and n are coprime The greatest common factor between x and n determines the expected result from the calculation xφ(n) (mod n)

  • If the GCF is 1, then the expected result is 1

  • If the GCF is n, then the expected result is 0

  • If the GCF is greater than 1 but not n, then the expected result is a multiple of the GCF.

Enter a value x: