2
$\begingroup$

Question: prove that for integers x and y there are no solutions to the modular equation $$ 9x + 10\equiv 6y - 1 \mod 15 $$

So my first thought was to assume that the congruence does have solutions, so 15 would divide the difference between the two equations. Meaning: $$ (9x + 10) - (6y - 1) = 15k \\ 9x - 6y + 11 = 15k $$ for some integer k. Then I notice that we have a lot of multiples of 3 here, so I rearrange it like this: $$ 11 = 15k - 9x + 6y \\ 11 = 3(5k - 3x + 2y) $$ This means 11 is an integer multiple of three. Clearly this is false, so we have arrived at a contradiction. Therefore there is no integer k such that $9x - 6y + 11 = 15k$, and thus the original modular equation has no solutions.

Is my logic valid? Is this the best way to prove this, or is there a more succinct and correct way? Thank you!

$\endgroup$
  • $\begingroup$ Can you solve the same equation modulo $3$? If you can solve it modulo fifteen, why should you be able to solve it modulo $3$? $\endgroup$ – Thomas Andrews Nov 6 '15 at 17:42
  • $\begingroup$ It is well done. However, it is important to get accustomed quickly to "modulo" language, it will make arguments smoother. $\endgroup$ – André Nicolas Nov 6 '15 at 17:52
2
$\begingroup$

The equation $$ 9x + 10\equiv 6y - 1 \mod 15 $$ can be immediately taken mod $3$ since $3 \mid 15$. This yields $$ 1 \equiv -1 \mod 3,$$ which is clearly false. So there are no such $x,y$.

Behind the scenes, this is precisely your answer. It just happens that one can get to it quite quickly.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.