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 [LaTeX ERROR: Convert failed] and
[LaTeX ERROR: Convert failed] ?

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

Now, are -3 and 4 the inverse of [LaTeX ERROR: Convert failed] and
[LaTeX ERROR: Convert failed] ?
Hmmm no !!!

You have $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 $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 [LaTeX ERROR: Convert failed]
[LaTeX ERROR: Convert failed] 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

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

From the second equation we have
$1=31-3\cdot 10$
$1 =31-3(41-31)$ by the first eq.
$
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:
$
\begin{array}{rcll} x & \equiv & 6 & \text{mod } 9 \\ x & \equiv & 3 & \text{mod } 13 \\ x & \equiv & 5 & \text{mod } 16 \end{array}
$

/Jones