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"

Means,

And this means,
for some .
This means,
where .
Let us find the smallest positive integral which solves this for .

First use die Euclidean algorithm.









Now continue.

Originally Posted by ThePerfectHacker

Means,

And this means,
for some .
This means,
where .
Let us find the smallest positive integral which solves this for .

First use die Euclidean algorithm.









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.