More Mods

What is the units digit for the number 123^(456) ?

N000ughty Thoughts

How many noughts are at the end of these giant numbers?

Mod 3

Prove that if a^2+b^2 is a multiple of 3 then both a and b are multiples of 3.

Novemberish

Stage: 4 Challenge Level:

These solutions, which use quite different methods, are by Ang Zhi Ping from River Valley High School in Singapore, Pierce Geoghegan from Tarbert Comprehensive in Ireland and Mohammad Afzaal Butt. Good work Ang Zhi, Pierce and Mohammad!

Mohammad provided us with this solution to part (a):

Observation 1:

Since $a$ and $b$ are digits, they can be any of $0$, $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$ or $9$. Since $aabb$ is a 4-digit number, $a$ cannot be $0$.

Observation 2:

$0^2 = 0$,
$1^2 =1$,
$2^2 =4$,
$3^2=9$,
$4^2=16$,
$5^2 =25$,
$6^2=36$,
$7^2=49$,
$8^2 =64$ and
$9^2 = 81$

These results tell us that $b$ can only be $0$, $1$, $4$, $5$, $6$ or $9$ because $aabb$ is a perfect square.

Observation 3:

We can write $aabb$ as:
\eqalign { aabb &= 1000a+100a+10b+b \cr &=1100a + 11b \cr &=11(100a+b)}Since $aabb$ is a perfect square $100a + b$ must be a multiple of $11$. We can also say that
$$100a + b = 99a + a + b$$ Here $99a$ is divisible by $11$, and $a + b$ must also be divisible by $11$. Since $a$ and $b$ are only single digits, this is only possible if$$a + b = 11$$ Since $b$ can only be $0$, $1$, $4$, $5$, $6$ or $9$ and $a+b=11$, we have that $a$ can be $2$, $5$, $6$ or $7$.

So our possible answers are $2299$, $5566$, $6655$ and $7744$. Of which, only $7744$ is a perfect square, which is the required result.

This solution to part (a) comes from Pierce Geoghegan:

$aabb = a(10^3)+ a(10^2) +b(10) + b = 11(b + 100a).$

Let $aabb = x^2.$ We know $x^2=0\ \rm{(mod\ 11)}$ and that implies $x^2 = 0\ \rm {( mod\ 121)}$ (since $11$ is prime $11^2$ must be a factor of $x^2$ ). So $x^2 = 121y^2$ for some integer $y$ and since $aabb < 10000$ we know $y< 10.$

Testing reveals $y=8$ and $aabb=7744$.

These solutions for part (b) use the Remainder Theorem and Modular Arithmetic. Can you prove the result using the Binomial Theorem, or yet another method?

This solution comes from Pierce Geoghegan.

For the second question note:

$11 = 11\ \rm{(mod\ 25)}$ ; $11^2 = -4\ \rm{(mod\ 25)}$ ; $11^3 = -19\ \rm{(mod\ 25)}$ ; $11^4 = 16\ \rm{(mod\ 25)}$ ; $11^5 = 1 \ \rm {( mod\ 25)}$ ... (A)

Now $11^{10}-1=(11^5 + 1)(11^5 - 1)$ and using (A)

$(11^5)- 1 = 0\ \rm {(mod\ 25)}$

Also $11^5 - 1=0\ \rm {(mod\ 2)}$ since $11^5=1\ \rm {(mod\ 2)}$ and $11^5 + 1=0\ \rm {(mod\ 2)}$ since $11^5=1\ \rm {(mod\ 2)}.$

So $(11^5 + 1)(11^5 - 1) = (0\ \rm{(mod\ 2)})(0\ \rm {(mod\ 50)}) = 0\ \rm {(mod\ 100)}.$ QED

This is Ang Zhi Ping's solution.

Let a polynomial $P(x)$ be $x^{10}-1$ . Observe that when $x=1$ , $P(x)$ is reduced to 0, ($1^{10}-1=0$). Hence, $(x-1)$ is a factor of $P(x)$ .

Thus, $11^{10}-1$ can be factorized to $(11-1)Q(x)$ , whereby $Q(x)$ is the quotient. We know by now, $11^{10}-1$ is a multiple of 10. Taking $x^{10}-1=(x-1)Q(x)$ , the quotient $Q(x)$ can be easily evaluated using synthetic division:

$x^{10}-1=(x-1)(x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1)$

Hence

$Q(x)= (x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1).$

One can see that when $x=1$ , the remainder of $Q(1)=10$ . Thus, $Q(x)=(x-1)R(x)+10$ and $(R(x)$ is another quotient. For $11^{10}-1$ , $P(x)=(x-1)((x-1)R(x)+10)$ which gives $P(11)=(11-1)((11-1)R(x)+10)=10(10R(x)+10)=100(R(x)+1).$

Thus, $11^{10}-1=100(R(x)+1)$ , and hence the number is a multiple of $100$.