Originally Posted by
Banana1 Hello,
I am just starting out with Number Theory and am struggling to work out congruence problems.
Im sure this one will be easy for most of you, but can you please quickly walk me through it?
3956x $\displaystyle \equiv$ 7 (mod 2351)
SIDE NOTE:
If you "Preview Post" and it looks ok, but
you exit before you "Submit Reply" then
all of the stuff you did for the preview will
evaporate (and no one will know of it).
What I intended to include:
1st step
We are looking for the modular inverse of
3956 and 2351. {ax + by = 1}
3956*x + 2351*y = 1
which will be equivalent to
3956*x $\displaystyle \equiv $ 1 mod 2351
Finding the inverse is just about as easy as finding the GCD
This is a very simple method to compute the modular inverse. If you end with a zero (in the r column) you will have the GCD(a,b) of ax+by
This is a very easy procedure to learn & use.
You may need additional comments if it is not clear.
Code:
Here the asterisk(*) means multiplication
Eqn a * x + b * y = r Operation
[ 1] 3956 * 1 + 2351 * 0 = 3956 [1]Equation
[ 2] 3956 * 0 + 2351 * 1 = 2351 [2]Equation
Equations [1] & [2] establish the initial values of x & y
Equation [3] = Equation [1] minus Equation [2]
[ 3] 3956 * 1 + 2351 * -1 = 1605 [1]-[2]
[ 4] 3956 * -1 + 2351 * 2 = 746 [2]-[3]
[4a] 3956 * -2 + 2351 * 4 = 1492 [4]*2 = [4a]
Eq[4a] is short version of multiple subtractions of Eq[4] minus Eq[3]
[ 5] 3956 * 3 + 2351 * -5 = 113 [3]-[4a]
[5a] 3956 * 18 + 2351 * -30 = 678 [5]*6=[5a]
(see 4a note)
[ 6] 3956 * -19 + 2351 * 32 = 68 [4]-[5a]
[ 7] 3956 * 22 + 2351 * -37 = 45 [5]-[6]
[ 8] 3956 * -41 + 2351 * 69 = 23 [6]-[7]
[ 9] 3956 * 63 + 2351 * -106 = 22 [7]-[8]
[10] 3956 * -104 + 2351 * 175 = 1 [8]-[9]
3956*(-104) + 2351*175 = -411424 + 411425 = 1
so
3956*(-104) $\displaystyle \equiv $ 1 mod 2351
since -104 is equivalent to (2351 - 104) mod 2351 it is 2247
3956*2247 $\displaystyle \equiv $ 1 mod 2351
2nd step
We actually need $\displaystyle 3956 x \equiv 7 mod(2351) $
which requires a multiply by 7
$\displaystyle 3956 (-104 \times 7) \equiv 7 mod(2351) $
-104 x 7 = -728;
2351 - 728 = 1623
Thus:
$\displaystyle 3956 \times 1623 = 6420588 = 7 + 2351 \times 2731 = 7 mod(2351) $
There are dozens of ways to calculate the modular inverse (& you can find almost all of them on the internet).
Review the algorithm above for computation of the Modular Inverse.
For pencil/paper this is the easiest procedure I have found that I can readily recall and use.