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, age 16, River Valley High School, Singapore and Pierce Geoghegan 17, Tarbert Comprehensive, Ireland. Good work Ang Zhi and Pierce!

(a) Here is Ang Zhe Ping's solution: A four-digit number (in base $10$) $aabb$ is a perfect square. Discuss ways of systematically finding this number. A four-digit base $10$ number, $aabb$ , whereby $a$ and $b$ are digits, could be written as:

$$ \eqalign { aabb &= 1000a+100a+10b+b \cr &=1100a + 11b \cr &=11(100a+b)} $$

Hence, the number $aabb$ is a multiple of $11$ and since $11(100a+b)$ is a multiple of $11$, and it has to be a square number, thus $100a+b$ is also divisible by $11$, and $(100a+b)/11$ has also to be another perfect square. Now $a$ and $b$ are digits, thus, they are integers ranging from $0$ to $9$. Also, as $100a + b$ is divisible by $11$ and $99a$ is divisible by $11$, we must have $a + b$ is divisible by $11$. So the only possible values of $100a+b$ are: $200+9=209=11 \times 19$ and $308$, $407$, $506$, $605$, $704$, $803$ and $902$.

Dividing these numbers by $11$:

$209 = 11 \times 19$;

$308 = 11 \times 28$;

$407 =11 \times 37$;

$506 = 11 \times 46$;

$605 = 11 \times 55$;

$704 = 11 \times 64$;

$803 = 11 \times 73$ and

$902= 11 \times 82$.

The only number in this list which is itself a square number ($11$ times a square number) is $704$ so the only number satisfying the required conditions is $7744$.

As observed, $700+4=704=11 \times 64$, thus, satisfying the conditions that $100a+b$ is a multiple of $11$, and $(100a+b)/ 11$ is another square ($64=8^2$). The number is $7744$, equal to $88^2$ .

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

(b) Prove that $11^{10}-1$ is divisible by $100$.

Editors note: These solutions use the Remainder Theorem and Modulus 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$.