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