You may also like

problem icon

More Mods

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

problem icon

N000ughty Thoughts

Factorial one hundred (written 100!) has 24 noughts when written in full and that 1000! has 249 noughts? Convince yourself that the above is true. Perhaps your methodology will help you find the number of noughts in 10 000! and 100 000! or even 1 000 000!

problem icon

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: Challenge Level:1

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