Suppose $x$ is an integer such that $3x \equiv 15 \pmod{64}$. If $x$ has remainder $2$ and quotient $q$ when divided by $23$, determine the remainder when $q$ is divided by $64$.
I tried a couple things. By division algorithm, know $x = 23q + 2$. So $3(23q + 2) \equiv 15 \pmod{64}$. Not sure how to go from there.
Another thing I tried is $3x = 64q + 15$. If we let $q$ be zero, then $x$ is obviously $5$. This also doesn't wind up being that helpful, and I think $x$ can have other values asides from $5$.
Best Answer
Use as many variables as you like, if you are not comfortable with the modulus notation. We can then work with them as ordinary equations, and see how to derive any conclusion.
For example, $3x \equiv 15 \mod 64$ means that $3x-15 = 64k$ for some integer $k$. Now, $3$ divides the left hand side, therefore the right as well. Using a lemma about primes, $3 | 64$ or $3 | k$. The former is not true, so $3 | k$ is true. Let $k = 3m$, then cancelling $3$ we get $x - 5 = 64m$.
Write $x = 23q + 2$. It follows that $23q = x - 2 = x-5+3 = 64m+3$.
So, $23q -3 = 64m$. What we will do now, is multiply both sides by a very special number, $39$. $$ 23q - 3 = 64m \implies 897 q - 117 = 64 \times 39m \implies q - 117 = 64 \times 39m - 64 \times 14q\\ \implies q = 64(39m - 14q) + 117 \implies q = 64(39m - 14q + 1) + 53 $$
Therefore, $q$ leaves a remainder of $53$ when divided by $64$.
Why did I multiply by $39$? What I wanted to do, actually, is to show that $q$ is a multiple of $64$ pus some remainder. The only way to isolate a single $q$ from the given equation, rather than $23q$, was so that I could remove exactly one $q$, and the remainder would be a multiple of $64$ (namely, $64 \times 14 = 896$) which I could send to the quotient side. The smallest number with which I could do this was $39$, since $23 \times 39 = 64 \times 14 + 1$.
$39$ is said to be the inverse of $23$ modulo $64$ for this reason.