See also page(s):

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.

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.

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.

ax

So x

That is if x

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 x

Solve 5x-3y=1 | |||||

k | x_{k} | y_{k} | r | q_{k} | 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 q _{2} column with r_{1} (mod r_{2})=-1, and write the remainder of the division as r_{3} below.Compute the next x and y values using: x _{3}=x_{1}−x_{2}•q_{2}=1−0•(-1)=1y _{3}=y_{1}−y_{2}•q_{2}=0−1•(-1)=1 |

3 | 1 | 1 | 2 | -1 | Compute the next q value, r_{2} mod r_{3}=-1, and write the next remainder, r_{4}=-1, below.Compute the next x and y values: x _{4}=x_{2}−x_{3}•q_{3}=0−1•(-1)=1y _{4}=y_{2}−y_{3}•q_{3}=1−(-1)•1=2 |

4 | 1 | 2 | -1 | -1 | Compute the next q value, r_{3} mod r_{4}=-1Write the remainder below, r _{5}=1Compute the next x and y values: x _{5}=x_{3}−x_{4}•q_{4}=1−1•(-1)=2y _{5}=y_{3}−y_{4}•q_{4}=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 | y_{k} | x_{k} | r | q_{k} |

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

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 ax

If we multiply by b, we get:

b•a•x

If we write x=bx

ax-km=b, where x=b•x

That is, to solve ax≡b (mod m) by first solving:

ax

Which we can do using Euclid, or other methods. And finding x from x=b•x

■

ax

Cancelling the a's, we find:

x

Therefore x

■

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 | y_{k} | x_{k} | r | q_{k} |

1 | 1 | 0 | 340 | |

2 | 0 | 1 | 3 | 113 |

3 | 1 | -113 | 1 |

From the table, we find a solution x

-226≡114 (mod 340), so the solution to

3x≡2 (mod 340)

is x≡114 (mod 340)

■

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.

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]

■

x

x=x

Therefore, there are d solutions to Equation 3.1

■

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

■

Number Theory Contents

Ken Ward's Mathematics Pages

No script follows:

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: