a = b mod m <=> m | (b - a) |
If a = b mod m and c = d mod m Then a+c = b+d mod m a-c = b-d mod m a.c = b.d mod m a^{n} = b^{n} mod m (with n > 0) n.a = n.b mod m |
If e divides a, b and m Then a = b mod m <=> a/e = b/e mod m/e |
If (k,m) = 1 Then ak = bk mod m <=> a = b mod m |
ak = bk mod m <=> m | (a-b)k since (k,m) = 1 <=> m | (a-b) <=> a = b mod m
ax = b mod m has a solution x <=> there is a k and an x such that ax - b = km <=> there is a k and an x such that ax - km = b <=> there is a linear combination of a and m that gives b. <=> b is a multiple of (a,m)The last assertion holds because all linear combinations of a and m are exactly all the multiples of (a,m)
ax = b mod m has a solution <=> b is a multiple of (a,m) |
Then d = (a,m) divides a, b and m. So, the equation can be simplified to
ax/d = b/d mod m/d <=> a'x = b' mod m' with (a',m')=1If (a',b') is k, then we can use the cancellation law, to simplify the last equation.
Example:
18x = 6 mod 8
(18,8)=2 is a divisor of 6. The solvability condition is satisfied.
Simplification law gives 9x = 3 mod 4 and the cancellation law gives
3x = 1 mod 4
Take the (m-1) multiples a ; 2a ; 3a ; ... ; (m-1)a all taken mod m .
All these multiples are different!
If for instance
3a = 5a mod m then canceling a we have 3 = 5 mod m and this is impossible
because 3 and 5 are smaller than m.
Hence, all these multiples are the numbers 1,2,3,...,m-1 in an arbitrary order.
Therefore, the equation ax = b mod m has just one solution modulo m.
In previous example, we try x = 1, 2 and 3 and we find that (3 mod 4) is the solution.
a^{x} = 1 mod mThe theorem of Fermat gives a solution for a special case.
If p is prime and (a,p)=1 then a^{(p-1)} = 1 mod p. |
Hence,
(1a)(2a)(3a)...((p-1)a)= 1.2.3. ... .(p-1) mod p
Since (1,p)=(2,p)=(3,p)=..(p-1,p)=1 , we can use the cancellation law.
So, a^{(p-1)} = 1 mod p
phi(m) = the number of positive integers n < m such that (n,m)=1. |
If p is prime then phi(p) = p-1 and phi(p^{2})=p.(p-1)
If (a,b)=1 then phi(a.b) = phi(a).phi(b) |
If (a,m) = 1 then a^{phi(m)} = 1 mod m. |
Proof:
Take all the numbers b from the set {1, 2, ... m} such that (b,m)=1.
Let b_{1}, b_{2},..., b_{n} be these numbers. n = phi(m) .
Take the multiples a.b_{1} mod m, a.b_{2} mod m, ...,a.b_{n} mod m
All these numbers are different!
If for instance
a.b_{i} = a.b_{j} mod m then from the cancellation law, we have
b_{i} = b_{j} mod m and this is impossible.
Additionally, each number a.b_{i} is relative prime to m since a and b_{i} are relative prime to m.
Therefore, these n different numbers
a.b_{1} mod m, a.b_{2} mod m, ...,a.b_{n} mod m
are the n different numbers relative prime to m.
So, these numbers are b_{1}, b_{2},... b_{n} in an arbitrary order.
Hence, (a.b_{1})(a.b_{2})...(a.b_{n}) = b_{1}.b_{2}. ... .b_{n} mod m
Using the cancellation law, we have a^{phi(m)} = 1 mod m
a^{n} = 1 mod mNow we make the euclidian division phi(m) : n. It gives us a quotient q and a remainder r. phi(m) = n.q + r with r < n or r = 0. Hence,
1 = a^{phi(m)} = a^{n q + r} = 1. a^{r} mod m => a^{r} = 1 mod mThis is impossible unless r = 0.
Thus phi(m) = n.q + 0 and n divides phi(m). Conclusion
The smallest strictly positive integer n such that
a^{n} = 1 mod mis a divisor of phi(m). |
a. x = b mod m multiply both sides with a^{phi(m)-1} <=> a.a^{phi(m)-1} . x = b.a^{phi(m)-1} mod m <=> x = b.a^{phi(m)-1} mod m b.a^{phi(m)-1} mod m is the unique solution!