# Problem with basic Linear Congruence

• Sep 17th 2007, 09:23 PM
BruceBronson
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??
• Sep 18th 2007, 08:42 AM
ThePerfectHacker
Quote:

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.
• Sep 18th 2007, 11:20 PM
BruceBronson
Quote:

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?
• Sep 19th 2007, 03:40 AM
topsquark
Quote:

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
• Sep 19th 2007, 06:39 PM
BruceBronson
Quote:

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"
• Sep 19th 2007, 07:48 PM
ThePerfectHacker
Quote:

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.
• Sep 20th 2007, 12:53 AM
BruceBronson
Quote:

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?
• Nov 6th 2007, 11:34 AM
AgentNXP
Alright--I am no Number Theorist, but here's my reasoning:

Quote:

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

Quote:

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. :D