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??
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
Alright--I am no Number Theorist, but here's my reasoning:
True! However, when you solved GCD(7642, 4871), it equaled 7. Not 1.Now this is a solution to the equation 4871x = 1 + 7642k. with x = 615 being 1 solution.
Therefore, when you used Euclidean's Algorithm...
...you wrote the linear combination as if GCD(7642, 4871)=1Using the euclidian algorithm on these numbers i get, 1 = 615 * 4871 - 392 * 7642. (Writing 1 as a linear combination of the two numbers)
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.