How to calculate the

• Dec 30th 2009, 12:36 PM
Hamster Jam
How to calculate the
...solution of a congruence with modulo notation from the reciprocal

Hey guys, new to the forum. I have been looking through my notes and I am stuck on an area of my number theory module.

I understand the modulo notation and for example that 14 ≡ 2 mod 12, etc etc.

I have the reciprocals (modulo 15):

1bar = 1
2bar = 8
3bar = No such x, also 5bar, 6bar, 9bar, 10bar, 12bar do not exist
4bar = 4
7bar = 13
8bar = 2
11bar = 11
13bar = 7
14bar = 14

I know this is just the reverse process but if someone could explain to me step by step how these solutions are found that would be great.

Thanks
• Dec 30th 2009, 03:27 PM
chiph588@
$\displaystyle (a,m)=1 \Longleftrightarrow \exists \; x,y \in \mathbb{Z} \text{ s.t. } ax+my=1$.

Hence $\displaystyle (a,m)=1 \Longleftrightarrow \exists \; x \in \mathbb{Z} \text{ s.t. } ax \equiv 1 \mod{m}$.

So your example demonstrates this fact and notice the reciprocal of $\displaystyle a$ can be found through the Euclidean algorithm.
• Dec 30th 2009, 06:39 PM
Soroban
Hello, Hamster Jam!

Here's a primitive (but very simple) approach . . .

Quote:

Finding reciprocals in modulo notation.

I have the reciprocals (mod 15):

. . $\displaystyle \begin{array}{ccc}\overline 1 &=& 1 \\ \overline 2 &=& 8 \\ \overline 4 &=& 4 \\ \overline7 &=&13 \\ \overline 8 &=& 2 \\ \overline{11} &=& 11 \\ \overline{13} &=& 7 \\ \overline{14} &=& 14 \end{array}$

No reciprocals for 3, 5, 6, 9, 10, or 12.

If someone could explain to me step by step
how these solutions are found, that would be great.

Let's find the reciprocal of 7.

We want a number $\displaystyle x$ such that: .$\displaystyle 7\!\cdot\! x \:\equiv\:1 \;\text{(mod 15)}$

That is: .$\displaystyle 7x \:=\:15a + 1$ for some integer $\displaystyle a.$

Solve for $\displaystyle x\!:\quad x \:=\:\frac{15a+1}{7} \quad\Rightarrow\quad x \:=\:2a + \frac{a+1}{7}$

Since $\displaystyle x$ is an integer, $\displaystyle a\!+\!1$ must be a multiple of 7.

The first time this happens is: .$\displaystyle a = 6$

Hence: .$\displaystyle x \:=\:2(6)+\frac{6+1}{7} \:=\:13$

. . Therefore, the reciprocal of 7 is 13 (in mod 15).

• Dec 31st 2009, 05:16 AM
HallsofIvy
I would do this slightly differently from Soroban. To find the reciprocal of 7 (mod 15) we need, as Soroban said, 7x= 15a+ 1 for some integers x and a. That is the same as the Diophantine equation 7x- 15a= 1. Now, 7 divides into 15 twice with remainder 1: 15= 2(7)+ 1 which is the same as (-2)(7)- (-1)15= 1 so that x= -2 is a solution. But we want a number between 0 and 14 so add 15: 15-2= 13 is between 0 and 15 and is equivalent to -2 (mod 15). As I said, only slightly different from Soroban.
• Jan 2nd 2010, 06:40 AM
Hamster Jam
Thanks for the replies! Using HallsofIvy's method, when I apply the method to an actual problem I am having trouble. please state where I am going wrong! Im guessing it's in calculating the reciprocals. Sorry about the poor notation!

x ≡ 3 (mod 4)
x ≡ 4 (mod 5)
x ≡ 2 (mod 7)

is the set of congruences I have to solve.

M = (4x5x7) = 140
M1 = (7x5) = 35
M2 = (4x7) = 28
M3 = (4x5) = 20

Now the reciprocals:

M1bar = 35bar ≡ 3bar (mod 4)

3x = 4a +1
3x - 4a =1
4 = 1(3) + 1
(-1)(3) - (-1)(4) =1
x = -1 is a solution. but we need a solution in between 0 and 2. so add 3,

M1bar = 2

now calculate M2bar = 28bar ≡ 3bar (mod 5)

3x = 5a +1
3x - 5a = 1
5 = 1(3) + 2
(-1)(3) - (-1)(5) = 2
x = -1 is a solution. add 5

M2bar = 4

now calculate M3bar = 20bar ≡ 6bar (mod 7)

6x = 7a +1
6x - 7a = 1
7 = 1(6) + 1
(-1)(6) - (-1)(7) = 1
x = -1 is a solution, but we add 7

M3bar = 6

using the formula
x ≡ a1*M1*M1bar+...+an*Mn*Mnbar (mod M)

I get x = (3*35*2) + (4*28*4) +(2*20*6)

x = 898 ≡ 58 (mod 140).

This answer is incorrect however.

A little bit more help required!

Thanks again