[Back] Euler's Theorem defines that \(a^{\phi} \equiv 1 \pmod N\), and where \(N= pq \), and \(\phi = (p-1) (q-1)\). \(N\) and \(a\) must be co-prime, and where they do not share any factors (\(gcd(N,a)=1\)):

## Euler's Theorem |

## Method

Euler's formula

\(a^{\phi} \equiv 1 \pmod N\)

where \(N\) is \(p q\), and \(\phi=(p-1)(q-1)\). The values of \(a\) and \(N\) must be co-prime.

If we try a value of \(a=7\), \(p=7\) and \(q=11\), \(a\) and \(N\) are co-prime, thus the result is 1:

a= 3 p= 7 q= 11 PHI= 60 ---------- N and a are co-prime, and this should work ---------- Result of a^{PHI} (mod N)= 1

If we try a value of \(a=3\), \(p=8\) and \(q=9\), \(a\) and \(N\) are NOT co-prime, thus the result will not be 1:

a= 3 p= 8 q= 9 PHI= 56 ---------- This will not work as N and a are not co-prime ---------- Result of a^{PHI} (mod N)= 9

## Code

An outline of the code used is:

import sys p=101 q=103 a=7 def gcd(a, b): while( b != 0 ): Remainder = a % b; a = b; b = Remainder; return a; N=p*q PHI=(p-1)*(q-1) res = gcd(N,a) val = a** (PHI) % N print "a=\t",a print "p=\t",p print "q=\t",q print "PHI=\t",PHI print "----------" if (res>2): print "This will not work as N and a are not co-prime" else: print "N and a are co-prime, and this should work" print "----------" print "Result of a^{PHI} (mod N)=",val