Originally Posted by
HallsofIvy Notice that the solutions, x= 4, 9, and 14, to 6x= 9 (mod 15) so NOT satisfy 2x= 3 (mod 15) but do satisfy 2x= 3 (mod 5). That is because the equation ChiSigma got, 6x= 9+ 15k, is the same as 2x= 3+ 5k.
Another way to solve the Diophantine equation, 2x- 5k= 3, useful for problem where the modulus is too large to conveniently "try" integer values for k, is to note that 2 divides into 5 twice with remainder 1. That is, 5(1)- 2(2)= 1 so that 2(-2)- 5(-1)= 1 and then, multiplying by 3, 2(-6)- 5(-3)= 3. That is, one solution is x= -6, k= -3. But notice that is we replace x with x+ 5n and y with y+ 2n, we have 2(x+ 5n)- 5(k+ 2n)= 2x+ 10n- 5k- 10n= 2x- 5k which equals three if and only if x and k satisfy the equation. That is, all solutions are of the form x= -6+ 5n. In particular, taking n= 2 3, and 4 give x= 4, 9, and 14, the three solutions between 0 and 15.