Finding the remainder using Division Algorithm?

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?

• 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! – Bram28 Jun 6 '17 at 21:52
• 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$. – N74 Jun 6 '17 at 22:07
• So you're not allowed to use modular arithmetic to solve the problem? – Dave Jun 6 '17 at 22:18
• @Dave sadly, no – 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$.