# Thread: Help with understanding congruence problems

1. ## Help with understanding congruence problems

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)

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

$\displaystyle 3956 \cdot x \equiv 7 \, mod(2351)$

means

3956x = 7 + 2351k

3956 times some number(x) is equal to 7 + 2351 times someother number(k)

The following shows how to find the value of x and the value of k.

3. Can anyone actually get the answer for this? Ive been playing around with it for ages and cant get it out.

4. Do you know the Chinese remainder theorem?
I'm not very good at calculation, so perhaps this method is not optimal. But that's how I'd do it.

Notice that if you find a solution to the system

$\displaystyle y \equiv 7 \mod 2351$
$\displaystyle y \equiv 0 \mod 3956$

Then $\displaystyle x=y/3956$ is a solution to your original system (can you see why?).
Since 3956, 2351 are coprime, the Chinese remainder theorem guarantees the existence of a solution; you can determine it fairly easily using the Euclidean algorithm.

Give this a try and report back if you still can't do it.

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