- Formula
- Example of Unsolvable (illogical) Equations
- Example of Simple Solvable Equations 1
- Example of Simple Solvable Equations 2
- Example Using Euclid
- Proof of Formula

For instance the set:

[1.1]

Or equivalently, the following

[1.2]

We note that the m's are not required to be relatively prime.

We define:

[1.3]

And the formula is:

[1.4]

Usually written in preparation for the solution:

[1.5]

Where n is a solution, mod M, if d= gcd (M

If m

a

a

Here M=36

k | m_{k} |
r_{k} |
M_{k} |
M_{k}r_{k} |

1 | 2 | 1 | 18 | 18 |

2 | 3 | 2 | 12 | 24 |

3 | 6 | 4 | 6 | 24 |

Σ= | 36 | 66 |

gcd(36,36)=36, which does not evenly divide 66, so there is no solution.

The equations are illogical because there is no integer which divided by 2 leaves a remainder 1, and when divided by 6 gives a remainder 4.

a

a

a

Here M=252

k | m_{k} |
r_{k} |
M_{k} |
M_{k}r_{k} |

1 | 2 | 1 | 126 | 126 |

2 | 3 | 2 | 84 | 168 |

3 | 6 | 5 | 42 | 210 |

4 | 7 | 5 | 36 | 180 |

M=252 | ΣM_{k}=288 |
ΣM_{k}r_{k}=684 |

gcd(288,684)=4, which divides the M

n≡684/288 mod (252)

It is often convenient to write this as:

288n≡684 mod (252)

Dividing by 4:

72n≡171 mod (63)

Casting out 63's:

9n≡45 mod (63)

Dividing by 9:

n≡5 mod (7)

The smallest number, that suits the problem, is therefore 5 modulo 42. The next solution is 5+42=47.

a

a

Here M=30

k | m_{k} |
r_{k} |
M_{k} |
M_{k}r_{k} |

1 | 2 | 1 | 15 | 15 |

2 | 3 | 2 | 10 | 20 |

3 | 5 | 4 | 6 | 24 |

M=30 | ΣM_{k}=31 |
ΣM_{k}r_{k}=59 |

gcd(31,30)=1, which divides the M

31·n≡59 (mod 30)

Casting out 30's:

n≡29 (mod 30)

The required number is therefore 29.

a

a

a

Here M=120

k | m_{k} |
r_{k} |
M_{k} |
M_{k}r_{k} |

1 | 2 | 1 | 60 | 60 |

2 | 3 | 2 | 40 | 80 |

3 | 4 | 3 | 30 | 90 |

4 | 5 | 2 | 24 | 48 |

M=120 | ΣM_{k}=154 |
ΣM_{k}r_{k}=278 |

gcd(120,154)=4, which divides the M

154n≡278 (mod 120)

Casting out 120's:

34n≡38 (mod 120)

Dividing by 2:

17n≡19 (mod 60)

As the answer isn't obvious, we use Euclid's Extended Algorithm, to solve:

17n−60l=1,

And then multiply the answer by 19, as when solving congruence equations.

k | l_{k} |
x_{k} |
r_{k} |
q_{k} |

1 | 1 | 0 | 60 | |

2 | 0 | 1 | 17 | 3 |

3 | 1 | -3 | 9 | 1 |

4 | -1 | 4 | 8 | 1 |

5 | 2 | -7 | 1 |

So x

x≡(−7)·19=−133 (mod 60)

x≡47 (mod 60)

The solution to the equations is therefore 47

We first seek to solve the equations:

N≡r

N≡r

N≡r

First we deal with the first two, by multiplying Equation 3.1 by m

N·m

N·m

Adding the equations, we have:

N·(m

The equation 3.6 above satisfies both equations 3.1 and 3.2

We can add Equation 3.3 to this equation by converting both to modulo m

N·(m

N·m

Adding these gives:

N·(m

Let M

We can therefore write equation 3.9 as:

N·(M

N≡r

N≡r

…

N≡r

Let us generalise 3.10 for n equations, so:

M=m

M

So Equation 3.10 is in general for n equations:

N·(M

For the case when N=1, we have:

M=m

M

And from 3.11:

N≡r

Which is our first equation of 3.A

When n=n, then we use the formula 3.11:

N·(M

When n=n+1, we add equation:

N≡r

To the list.

To add this equation to 3.11, we multiply 3.11 by m

N·m

and

N·(M

Now we can add 3.13 and 3.14 because they have the same modulus:

N·(M

Now we note that the new M=M·m

Therefore 3.15 can be written:

N·(M

Which is what our equation would predict.

Therefore, if the formula is correct for n=any natural number, then it is true for n+1. It is true for n=1, so it is true for n=2. In which case, it is true for n=3, and so on for all natural numbers.

■

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: