Suppose $x$ is an integer such that $3x \equiv 15 \pmod{64}$. Find remainder when $q$ is divided by $64$.

Question

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$.

Answer 1

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.

Answer 2

$3x\equiv 15\pmod{64}$ means
$64\mid (3x-15)$
$64\mid 3(x-5)$

Since $64$ and $3$ have no common factors, it follows that $64$ must divide the remaining factor $x-5$ : $$x\equiv 5\pmod {64}$$

Directly plugin the given info $x=23q+2$ : $$23q+2\equiv 5 \pmod{64}$$

Subtract $2$ both sides and see if you can try the rest.

Answer 3

By division algorithm, know $x = 23q + 2$. So $3(23q + 2) \equiv 15 (mod 64)$.

Hint:   then $\,15 = 69 q + 6 \equiv 5q + 6 \pmod{64} \implies 5q \equiv 9 \implies 65q \equiv 117 \implies \ldots\,$

Answer 4

Continuing from where you stopped: $$\begin{align} 3(23q + 2) &\equiv 15 \pmod{64} \Rightarrow \\ 69q+6 &\equiv 15 \pmod{64} \Rightarrow \\ 69q &\equiv 9 \pmod{64} \Rightarrow \\ 64q+5q &\equiv 9 \pmod{64} \Rightarrow \\ 5q &\equiv 9 \pmod{64} \Rightarrow \\ 5q\cdot 13 &\equiv 9\cdot 13 \pmod{64} \Rightarrow \\ 65q &\equiv 117 \pmod{64} \Rightarrow \\ 64q+q &\equiv 64+53 \pmod{64} \Rightarrow \\ q &\equiv 53 \pmod{64}. \end{align}$$