4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ So $69q+6\equiv 5q+6\equiv 15\mod 64$. So $5q\equiv 9\mod 64$. Add or subtract 64 from 9 to get a multiple of 5. I'd do $5q\equiv 9-64 =-55 \mod 64$. So $q\equiv -11\equiv 53 \mod 64$ $\endgroup$
    – fleablood
    Jul 19, 2018 at 6:20

4 Answers 4

Reset to default
3
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Is there an easy way to calculate the inverse of any modulo expression? $\endgroup$
    – SolidSnackDrive
    Jul 19, 2018 at 19:23
  • $\begingroup$ I would also like to know if we can still find the inverse even in the case where $ax \equiv r \text{ mod} p $, such that gcd$(a,p) \neq 1$ $\endgroup$
    – john fowles
    Jul 19, 2018 at 21:08
  • $\begingroup$ @SolidSnackDrive It can be done using the reverse Euclidean algorithm. Essentially, you perform the Euclidean algorithm used to find the gcd of two numbers, and then a "reverse substitution" gives you the desired inverse. Taking a small example, if you want the inverse of $4$ modulo $7$, then we do : $7 = 1 \times 4 + 3$, and $4 = 1 \times 3 + 1$. Now, $1 = 4 - 3 = 4 - (7 - 4) = 2 \times 4 - 7$, so $2 \times 4 = 1 \times 7 + 1$ ,and the inverse of $4$ is $2$. However, read my next comment. $\endgroup$
    – Sarvesh Ravichandran Iyer
    Jul 21, 2018 at 3:14
  • $\begingroup$ @johnfowles If $\gcd(a,p) \neq 1$, then solutions to the equation you have given exist if and only if $r$ is a multiple of the gcd also. For example, there are no solutions to $2x \equiv 3 \mod 4$, since $\gcd(2,4) = 2$ but $3$ is not a multiple of $2$. IF $r$ is a multiple, then write $n = \gcd(a,p)$, so $r = kn$. Now, $ax \equiv kn \mod p$, so $ax - kn = lp$ for some $l$. Now, if $a = bn$ and $p = qn$, then we can cancel $n$ to get $bx - k = lq$, or $bx \equiv k \mod q$, where $\gcd(b,q) = 1$. Back to square one : solve for $x$! This $x$ will also satisfy the earlier equation. $\endgroup$
    – Sarvesh Ravichandran Iyer
    Jul 21, 2018 at 3:19
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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\,$

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