# Math Help - How to calculate the

1. ## 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

2. $(a,m)=1 \Longleftrightarrow \exists \; x,y \in \mathbb{Z} \text{ s.t. } ax+my=1$.

Hence $(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 $a$ can be found through the Euclidean algorithm.

3. Hello, Hamster Jam!

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

Finding reciprocals in modulo notation.

I have the reciprocals (mod 15):

. . $\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 $x$ such that: . $7\!\cdot\! x \:\equiv\:1 \;\text{(mod 15)}$

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

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

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

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

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

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

4. 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.

5. 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).