Let: ax≡b (mod m) [1.1] If a ⊥m (where , ⊥ means relatively prime) then 1.1 has a solution. This is because we can divide by a, and obtain an expression for x. Otherwise, if gcd(a,m)=d>1, then there is a solution if d|b. That is we can divide by a and obtain an expression for x. (Actually, there are d solutions). In other cases, there is no solution.
Examples
For instance: 2x≡3 (mod 7), gcd(2,7)=1, so we can divide by 2. By running through the tables for mod 7, we find: x≡5 (mod 7) This solution is unique mod 7, as can be verified by checking the complete residue system for 7. ■
6x≡4
(mod 3) has no solution because gcd(6,3)=3, and 3 does not divide 4.
Also, reducing the equation by casting out 3's, we find 0≡1 (mod
3), or 3x≡1 (mod 3), and there are no numbers, mod 3, which when
multiplied by 3 give 1, which we can check for all the possible values
0, 1, 2, So there are no solutions. ■
However 4x≡4 (mod 12),
has gcd(4,12)=4, which divides 4, so there is a solution to this
equation. In fact, as we shall see later, there are 4 solutions mod 12.
Solutions when a and m are coprime (or relatively prime)
Suppose:ax≡b (mod m) Where gcd(a,m)=1, that is a⊥m, and we seek the value of x (mod m) Using Definition 1.2: ax=b+km So, ax-km=b
Alternatively, because ax≡b (mod m)↔b≡ax (mod m), because they are equivalent. then we can write ax-km=b as ax+km=b, with a change in sign for k.
If b=gcd(a,m)=1, we have: ax-km=1 According to Euclid's Extended Algorithm, then there are numbers which satisfy x and k. That is: ax≡1 (mod m) has solutions for x when a and m are relatively prime.
Unique Solution
Suppose x1 is one solution and x2 is another solution, then ax1≡1 ≡ax2 (mod m) So x1≡x2 (mod m). We can divide by a, because, from above, a and m are relatively prime, so the cancellation rule applies. That is if x1 is a solution, and x2 is any other solution, then x2 is equivalent to x1, and x1 is therefore unique.
Euclid's Extended Algorithm
Euclid's Extended Algorithmcan be used to solve equations of the form: ax+by=1 And need's to be used when a and b are large numbers. Here we use the algorithm to solve: 5x−3y=1 (5x≡1 (mod 3), which is easily solved by testing. In the table below, I have written xk
first, because its coefficient is greater than that of y. In the second
example, the order is reversed because the coefficient of the xk is smaller than the coefficient of the y.
Solve 5x-3y=1
k
xk
yk
r
qk
Comments
1
1
0
5
First write down the larger number (5) and fill in the x and y columns with 1 and 0, respectively.
2
0
1
-3
-1
Write down the next number, (3) and fill in the x and y columns with 0 and 1 respectively. Also fill in the q2 column with r1 (mod r2)=-1, and write the remainder of the division as r3 below. Compute the next x and y values using: x3=x1−x2•q2=1−0•(-1)=1 y3=y1−y2•q2=0−1•(-1)=1
3
1
1
2
-1
Compute the next q value, r2 mod r3=-1, and write the next remainder, r4=-1, below. Compute the next x and y values: x4=x2−x3•q3=0−1•(-1)=1 y4=y2−y3•q3=1−(-1)•1=2
4
1
2
-1
-1
Compute the next q value, r3 mod r4=-1 Write the remainder below, r5=1 Compute the next x and y values: x5=x3−x4•q4=1−1•(-1)=2 y5=y3−y4•q4=1−(-1)•2=3
5
2
3
1
We now have the remainder 1, so we are finished. x=2, and y=3
The
equation 9x≡1 (mod 256) is not so easy to solve through testing, and is
one which requires us to use Euclid's Extended Algorithm.
Solve 9x-256y=1
k
yk
xk
r
qk
1
1
0
-256
2
0
1
9
-28
3
1
28
-4
-2
4
2
57
1
From the table, we note that x=57, and in 9x≡1 (mod 256), the solution is equivalent to 57. Check: 9•57=513=2•256+1
Now, suppose that ax0-k0m=1 If we multiply by b, we get: b•a•x0-b•k0•m=b
If we write x=bx0 and k=bk0, then ax-km=b, where x=b•x0, and k=b•k0
That is, to solve ax≡b (mod m) by first solving: ax0-k0m=1
Which we can do using Euclid, or other methods. And finding x from x=b•x0, ■
Unique Solution
The solution is unique, because, if x1 is a solution, and x2 is any other solution, we find: ax1≡b≡ax2 (mod m) Cancelling the a's, we find: x1≡x2 (mod m)
Therefore x1 is a unique solution, because any other solution is equivalent. ■
Examples
3x≡5 (mod 7) By testing, we find that x≡4 Of course, we do not need to use Euclid. ■
3x≡2 (mod 340) We probably need to use Euclid, because trial and error would be time consuming. We need to solve: 340y+3x=1, first
Solve 340y+3x=1
k
yk
xk
r
qk
1
1
0
340
2
0
1
3
113
3
1
-113
1
From the table, we find a solution x3=-113, so, 3x≡2 (mod 340), has a solution -113•2=-226 -226≡114 (mod 340), so the solution to 3x≡2 (mod 340) is x≡114 (mod 340) ■
Solutions when a and m are not coprime
Let x≡b (mod m) where gcd(a,m)=d>1. But, of course, d | b, because by definition m|(ax-b), and if d divides m, and d divides a, then d must divide b.
Let k, an integer, be such that k =(ax-b)/m, so ax-b=km. As d divides a and m, let a=rd and m=sd So, rdx-b=ksd d(rx-ks)=b Now
as d divides the left-hand side, it must divide the right hand side,
which by our assumption, it does not. As it is false that d does not
divide b, it must be true that d divides b, otherwise, the equation
ax≡b (mod m), with gcd(a,m)=d>1 and d does not divide b has no
solution.
In ax≡b (mod m) [3.1] Let a=rd, and m=sd, and b=td, where r, s are relatively prime rdx≡td (mod sd) We can divide throughout by d: rx≡t (mod s) In
this case, we have an equation where r and s are relatively prime,
which we can solve in the above manner. We can rewrite the equation as: rx≡t (mod m/d) [3.2] ■
Number of Solutions
Because r and m/d are relatively prime in 3.2, the equation has a unique solution, say x0 (mod m/d). However, mod m, it has the following solutions: x0, x0+m/d, x0+2m/d, ... x0+(d-1)m/d, which number d. In general, x=x0+km/d, where k=0, 1, 2, 3, 4, ... d-1
Therefore, there are d solutions to Equation 3.1 ■
Examples
6x≡12 (mod 12) gcd(6,12)=6, which divides 12, so the equation has a solution. Dividing by 6, we find: x≡2 (mod 2)≡0
There are six (d) solutions (mod 12): 0, 2, 4, 6, 8, and 10 ■
14x≡7 (mod 28) gcd(14,28)=14, which does not divide 7, so there are no solutions.
14x≡7 (mod 35). gcd(14,35)=7, which divides 7, so the equation has solutions. Dividing by 7, we get: 2x≡1 (mod 5) x=3, by testing. (mod 5). There are 7 solutions (mod 35), which are: 3, 8, 13, 18, 23, 28, 33 ■
39x≡27 (mod 123) [4.1] gcd(39,123)=3, which divides 27, so there are solutions.
Dividing by d=3: 13x≡9 (mod 41) 13x+41y=9 [4.2]
First solving 13x+41y=1 [4.3]
Solving 13x+41y=1
k
y
x
r
q
1
1
0
41
2
0
1
13
3
3
1
-3
2
6
4
-6
19
1
The solution to 4.3, is x=19. The solution to 4.2 is: 19•9≡171 (mod 41) ≡7 (mod 41)
For Equation 4.1, we have 3 solutions (mod 123): 7, 48, 89 ■
