How would I solve this using just the division algorithm?

Let $x$ be an integer such that the remainder of $x$ divided by $99$ is $80$. Determine with proof, the remainder of $x^2 + 5$ divided by $99$

My work so far:

$x = y(99) + 80$
$x^2 +5 = z(99) + r$ where $r$ is the remainder

Substituting $x$ for $y(99) + 80$ and rearranging and simplifying ends us with: $8910y^2 + 7920y + 6405 - 99z = r$ which seems wrong due to the fact that there's so many variables. Is there a better way to solve this?

  • $\begingroup$ Given that the remainder of $x$ divided by 99 is 80, the remainder of $x^2$ will be the remainder of $80^2=6400$ divided by 99 ... so that is 64 ... And then just add 5 to that: 69. No variables needed at all! $\endgroup$ – Bram28 Jun 6 '17 at 21:52
  • 1
    $\begingroup$ You should not simplify: instead of $8910y^2 + 7920y + 6405 - 99z = r$ , use $99*99*y^2 + 2*99*80*y + 80*80 +5 =99z +r$ so $ 80*80 +5 =99(z -99*y^2 -2*80*y )+r$ so , grouping all terms multiple of 99 into $z$, $r=6405-99z$. Choosing $z=64$ you have $r=69$. $\endgroup$ – N74 Jun 6 '17 at 22:07
  • $\begingroup$ So you're not allowed to use modular arithmetic to solve the problem? $\endgroup$ – Dave Jun 6 '17 at 22:18
  • $\begingroup$ @Dave sadly, no $\endgroup$ – Spencer Chow Jun 6 '17 at 22:24

Here is a solution using the division algorithm: Since $x$ has a remainder of $80$ when divided by $99$, there exists $k\in\Bbb Z$ such that $x=99k+80$. Thus, we have: $$\begin{align}x^2+5&=(99k+80)^2+5\\&=99^2k^2+2\times99\times 80k+80^2+5\\&=99(99k^2+2\times80k)+80^2+5\\&=99(99k^2+2\times80k)+6405\\&=99(99k^2+2\times80k)+64\times 100+5\\&=99(99k^2+2\times80k)+64(99+1)+5\\&=99(99k^2+2\times80k)+64\times 99+64+5\\&=99(99k^2+2\times80k+64)+64+5\\&=99(99k^2+2\times80k)+69\end{align}$$ Then, since $99k^2+2\times80k$ is an integer, and since $0\leq 69<99$, we see that $69$ is the unique remainder (as dictated by the Division Algorithm) for $x^2+5$ when divided by $99$.

This solution just uses the starting point of the division algorithm, which is what you used by writing $x=99k+80$ for some $k$. Then, you just take this, and manipulate it into an expression for $x^2+5$. The key part is to group everything that has a $99$ (i.e. factor $99$ out of everything that you can after expanding the brackets and such).

Here is another solution (similar) involving modular arithmetic: We have that $$\text{The remainder of $x$ when divided by $99$ is $80$}\iff x\equiv 80\mod 99$$ Thus, $x^2\equiv 80^2\mod 99$ and $x^2+5\equiv 80^2+5\mod 99$. Since $80^2+5=6405$ we now have to find what $6405$ is equal to modulo $99$. One way to do this (without guess and check or a calculator) is by the following: $$\begin{align}6405&=64\times 100+5\\&=64\times(99+1)+5\\&=64\times 99+64+5\\&\equiv 64+5\mod 99\\&\equiv 69\mod 99\end{align}$$ Thus, the remainder of $x^2+5$ when divided by $99$ is $69$.


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.