# Thread: Modulo calculation and Euclid's algorithm

1. ## Modulo calculation and Euclid's algorithm

Hi,

im having some difficulties when trying to calculate the modulo inverse.

for example:
X = 12 mod 31
X = 20 mod 41 (I don't know how to write that in LaTex =/)

So we need to find u and v such that 31u + 41v = 1

They're both co-prime. My problem is that i don't understand how to run the Euclid's algorithm "backwards"

/Best regards Jones

2. Hello,
Originally Posted by Jones
Hi,

im having some difficulties when trying to calculate the modulo inverse.

for example:
X = 12 mod 31
X = 20 mod 41 (I don't know how to write that in LaTex =/)

So we need to find u and v such that 31u + 41v = 1

They're both co-prime. My problem is that i don't understand how to run the Euclid's algorithm "backwards"

/Best regards Jones
Here is how I do.

You know that when you finish the Euclidian algorithm, you'll get the gcd of 41 and 31 as a remainder, namely 1.

Start from the greatest integer :
41=31+10 ----> 10=41-31
In each step, write what the remainder is. Then continue the Euclidian algorithm :
31=10x3+1
Write the remainder :
1=31-10x3

But you know what 10 is. So substitute it in 1 :
1=31-3x(41-31) = 31-3x41+3x31=4x31-3x41
What's the point of all of this ? It's that you can express any remainder in terms of 41 and 31.

So from 1=4x31-3x41, you have u and v.

3. Thank you so much Moo!

Now, are -3 and 4 the inverse of $\displaystyle x \equiv 12 mod 31$ and
$\displaystyle x \equiv 20 mod 41$ ?

4. Originally Posted by Jones
Thank you so much Moo!

Now, are -3 and 4 the inverse of $\displaystyle x \equiv 12 mod 31$ and
$\displaystyle x \equiv 20 mod 41$ ?
Hmmm no !!!

You have $\displaystyle x=4 \times 31-3 \times 41$

The inverse of 12 mod 31 can be calculated this way :
we need to find a such that $\displaystyle 12a \equiv 1 \bmod 31$

---------------------------------------
But looking further into your problem, I don't see why you need to find u and v in 31u+41v=1.. is there an explanation on this in your notes ?

5. Hi,

Well i need to solve the equation $\displaystyle X \equiv 12 mod 31$
$\displaystyle X \equiv 20 mod 41$ and i am not sure how to do it. My book states that you need to find the largest common divider, which is 1 and run the Euclid's algorithm backwards to find the inverse....Sigh, isn't there an easier way?

6. Originally Posted by Jones
Hi,

So we need to find u and v such that 31u + 41v = 1

/Best regards Jones

$\displaystyle 41=1\cdot 31+10\\31$
$\displaystyle 31=3\cdot 10+1$
$\displaystyle 10=10\cdot 1+0$

From the second equation we have
$\displaystyle 1=31-3\cdot 10$
$\displaystyle 1 =31-3(41-31)$ by the first eq.
$\displaystyle 1=4\cdot 31-3\cdot 41$

7. Are there any general formula for the solutions, if there are more than one solution?

Could you please show me one more time. For example this modulo congruence system:
$\displaystyle \begin{array}{rcll} x & \equiv & 6 & \text{mod } 9 \\ x & \equiv & 3 & \text{mod } 13 \\ x & \equiv & 5 & \text{mod } 16 \end{array}$

/Jones