Euler's Theorem defines that \( a^{N-1} \equiv 1 \pmod N\). \(N\) and \(a\) must be co-prime, and where they do not share any factors (\(gcd(N,a)=1\)) [Euler for RSA]:
Euler's Theorem |
Method
Euler's formula
\(a^{N-1} \equiv 1 \pmod N\)
If we try a few examples we get:
>>> print 6**(6) % 7 1 >>> print 7**(10) % 11 1 >>> print 3**(16) % 17 1
If \(a\) and \(N\) share a factor, the formula will not work:
>>> print 5**(14) % (15) 10
If we make \(N\) a prime number, we will only have a problem when \(a\) is equal to the prime number (\(N\)).