Notice that if and only if if and only if . That is it! We found the solution. When we write it means for some . Therefore, all solutions to have the form .[/quote]
So if I understand this correctly, in the case 6x is congruent to 10 (mod 15), then there is no solution since 6 never divides evenly into 10+15k, where k is an integer.
The congruence never has a solution. So see this say there is such an then which means for some . But then . This is a problem because has no factor of .
Once you understood what I wrote above try generalizing the result. Let be positive integers and consider . Let . Prove that if the congruence is solvable then divides .