nav.gif (1245 bytes)mathematics

Ken Ward's Mathematics Pages

Number Theory Linear Congruence Equations (Indeterminate Equations)

Number Theory Contents
See also page(s):

Page Contents

  1. Linear Congruence Equations
    1. Solutions when a and m are coprime (or relatively prime)
    2. Euclid's Extended Algorithm
    3. Solutions when b≠1
    4. Solutions when a and m are not coprime


Linear Congruence Equations

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 Algorithm can 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
kxkykrqkComments
1105First write down the larger number (5) and fill in the x and y columns with 1 and 0, respectively.
201-3-1Write 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
3112-1Compute 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
412-1-1Compute 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
5231We 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
kykxkrqk
110-256
2019-28
3128-4-2
42571

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

Solutions when b≠1

Suppose:
ax≡b (mod m)

Where a and m are relatively prime, and b≠1

Using the definition:
ax=b+km, we have:
ax-km=b

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
kykxkrqk
110340
2013113
31-1131

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
kyxrq
11041
201133
31-326
4-6191

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






Number Theory Contents

Ken Ward's Mathematics Pages


Faster Arithmetic - by Ken Ward

Ken's book is packed with examples and explanations that enable you to discover more than 150 techniques to speed up your arithmetic and increase your understanding of numbers. Paperback and Kindle:
Buy now at Amazon.com
Faster Arithmetic for Adults