Thread: Problem with basic Linear Congruence

Hi, I'm trying to find all solutions to the equation 4871x=(mod7642) (congruent with).

Using the euclidian algorithm on these numbers i get, 1 = 615 * 4871 - 392 * 7642. (Writing 1 as a linear combination of the two numbers),

Now this is a solution to the equation 4871x = 1 + 7642k. with x = 615 being 1 solution.

The solution in the answers simply states "a solution to the original congruence is given by 7 x 615 = 4305. As gcd(4871,7642)=1 the solution will be unique modulo 7615 and all solututions are given by x = 4305 (mod 7642)"

I do not understand this solution at all?, Why are we choosing to multiply "x" by 7? Where does the 7615 come from??

Originally Posted by BruceBronson

Hi, I'm trying to find all solutions to the equation 4871x=(mod7642) (congruent with).

There are several ways to approach this. One is with the Chinese Remainder Theorem. But I cannot help you because you do not say what 4871x is congruent to.

Originally Posted by ThePerfectHacker

There are several ways to approach this. One is with the Chinese Remainder Theorem. But I cannot help you because you do not say what 4871x is congruent to.

4871x Is Congruent with (mod7642)

I'm not familiar with the Chinese remainter theorm, i was trying to turn it into a linear diophantine equation and solve it that way. can you please help?

Originally Posted by BruceBronson

4871x Is Congruent with (mod7642)

In order for a number to be "congruent" you need to specify what number it is congruent to. To put this in more familiar terms you are saying something on the order that "4871x = " and you aren't completing the RHS of the equation.

For example, you could potentially solve your stated problem by saying that "4871x is congruent to 1234 (mod 7642)." If you want to say that 4871x is divisible by 7642 then you say "4871x is congruent to 0 (mod 7642)."

-Dan

Originally Posted by topsquark

In order for a number to be "congruent" you need to specify what number it is congruent to. To put this in more familiar terms you are saying something on the order that "4871x = " and you aren't completing the RHS of the equation.

For example, you could potentially solve your stated problem by saying that "4871x is congruent to 1234 (mod 7642)." If you want to say that 4871x is divisible by 7642 then you say "4871x is congruent to 0 (mod 7642)."

-Dan

Sorry 4871x is congruent with 1 Mod 7642,

I just assumed if theres nothing there it assumes "1"

Originally Posted by BruceBronson

Sorry 4871x is congruent with 1 Mod 7642,

I just assumed if theres nothing there it assumes "1"

$\displaystyle 4871x \equiv 1 (\bmod 7642)$
Means,
$\displaystyle 7642|(4871x - 1)$
And this means,
$\displaystyle 4871x - 1 = 7642z$ for some $\displaystyle z\in \mathbb{Z}$.
This means,
$\displaystyle 4871x + 7642 y = 1$ where $\displaystyle y=-z$.
Let us find the smallest positive integral which solves this for $\displaystyle x$.

First use die Euclidean algorithm.
$\displaystyle 7642 = 1\cdot 4871 + 2771$
$\displaystyle 4871 = 1\cdot 2771 + 2100$
$\displaystyle 2771 = 1\cdot 2100 + 671$
$\displaystyle 2100 = 3\cdot 617 + 87$
$\displaystyle 617 = 7\cdot 87 + 8$
$\displaystyle 87 = 10\cdot 8 + 7$
$\displaystyle 8 = 1\cdot 7 + 1$
$\displaystyle 7 = 7\cdot 1 + 0$

Now continue.

Originally Posted by ThePerfectHacker

$\displaystyle 4871x \equiv 1 (\bmod 7642)$
Means,
$\displaystyle 7642|(4871x - 1)$
And this means,
$\displaystyle 4871x - 1 = 7642z$ for some $\displaystyle z\in \mathbb{Z}$.
This means,
$\displaystyle 4871x + 7642 y = 1$ where $\displaystyle y=-z$.
Let us find the smallest positive integral which solves this for $\displaystyle x$.

First use die Euclidean algorithm.
$\displaystyle 7642 = 1\cdot 4871 + 2771$
$\displaystyle 4871 = 1\cdot 2771 + 2100$
$\displaystyle 2771 = 1\cdot 2100 + 671$
$\displaystyle 2100 = 3\cdot 617 + 87$
$\displaystyle 617 = 7\cdot 87 + 8$
$\displaystyle 87 = 10\cdot 8 + 7$
$\displaystyle 8 = 1\cdot 7 + 1$
$\displaystyle 7 = 7\cdot 1 + 0$

Now continue.

Thats exactly what i did, now i get x=615. But the solution multiplies this by 7 to give x=4035 as a unique solution. Why is this multiplied by 7? It also says this solution is "unique modulo 7615" Is this definetly a mistake?

Alright--I am no Number Theorist, but here's my reasoning:

Now this is a solution to the equation 4871x = 1 + 7642k. with x = 615 being 1 solution.

True! However, when you solved GCD(7642, 4871), it equaled 7. Not 1.


Therefore, when you used Euclidean's Algorithm...

Using the euclidian algorithm on these numbers i get, 1 = 615 * 4871 - 392 * 7642. (Writing 1 as a linear combination of the two numbers)

...you wrote the linear combination as if GCD(7642, 4871)=1

As you solved, and as I restated above, this GCD is equal to 7, not 1.

Generally, when you use the Euclidean Algorithm, you assume it is equal to 1, but then adjust it, so that the final equation is equal to the GCD (in this case 7).

Therefore:
1 = 615 * 4871 - 392 * 7642 (with GCD=1)
(7 * 1) = [(7 * 615) * 4871] - [(7 * 392) * 7642] (with GCD=7)

A simple multiplication of both sides of the equation by 7 'corrects' the equation.


To answer your second (original) question, I feel '7615' is a typo.