numbertheory

7.3 Euler's Theorem
Theorem 7.5 Euler. If
(n)
n 1 and gcd(a,n) = 1, then a
1 (mod n) where (n) is Euler's
(Definition 7.1. For n 1, let (n) denote the number of positive
Phi-Function

integers not exceeding n that are relatively prime to n)

Ch 10 Introduction to Cryptography. From pg 204 of Elementary Number Theory, Sixth Ed. Burton
"The assumption that gcd(M,n) = 1 was made to use Euler's theorem. In the unlikely event that M and n
are not relatively prime, a similar argument establishes that j
(mod ) and r j
r
M
p
M (mod q),
which then yields the desired congruence r j M (mod n). We omit the details. "
Question:
Given Mk r mod n where M < n , and n = pq where p,q are distinct primes, kj 1 mod (n), and
gcd(M,n) > 1, prove that r j M mod n
k
k
r mod n, thus M j j
M
r mod .
n kj 1 mod (n) kj = 1 + (n) L for some L
k j
If L = 0 , then kj = 1, thus M
= M r j mod n r j M mod n. So now let L > 0, then
k j
j
j
k j
1+ (n) L
(n) L
M
r mod n r M
mod n M
mod n M (M
) mod .
n Thus we need to show that
(n) L
M (M
) M mod .
n gcd(M,n) > 1 and M < n implies that gcd (M,n) = p, or gcd (M, n) = q.
Note if gcd(M, n ) = M, then since M < n that M = p or M = q which is dealt with in the previous cases.
Now assume gcd ( M,n) = p so let M = pT, for some T where T < q and gcd (T,q) = 1 since if T q,
then M = pT pq = n which contradicts M < n and if gcd (T,q) = d >1, then since only 1 | q and q | q
thus d = q so q | T which contradicts T < q. Now gcd (T,q) = 1 q doesn't divide T so by Theorem 5.1
q 1
-
q 1
-
q 1
(Fermat's Theorem) T
1mod q and p
1mod q which imply (pT) - 1mod q, thus since M = pT we
q 1
-
(q 1
- )( p 1
- )
can write M
1mod q M
1mod .
q (n) = (pq) = (p)(q) = (p-1)(q-1), thus
(q 1
- )( p 1
- )
(n)
(n) L
(n) L
(n) L
M
1mod q M
1mod q and M
1mod q q | M
- 1 q | (M
- 1)M
(n) L
q | M(M
) - M.
(n) L
(n) L
(n) L
M = pT p | M p | M(M
- 1) p | M(M
) - M. Since p | M(M
) - M and
(n) L
(n) L
(n) L
q | M(M
) - M where gcd(p,q) = 1 then pq = n | M(M
) - M, thus M(M
) M mod n
which was needed. By a similar argument if gcd ( M, n ) = q, we can come to the same conclusion.
j
(n) L
Therefore r M (M
) mod n M mod n

---

---