Weekly Problem Archive
We got some lovely, solutions to and
thoughts on this problem at various levels.
One of our younger users, Molshree from
acland burley school, worked on a related problem by finding out
when solutions could be found when the operation of 'power' in the
problem was replaced by the operation of 'times'. Another younger
student, Rohan from Firs primary also worked on a related problem
in which he found numbers adding to 10.
Daniel, from Savile Park Primary sent in a
delightful solution in which he constructed a table of the units
digit in each case, from which he proved all of the results. He
writes:
Writing powers in mod 10 (units digits)
| $n$ |
$9^n$ |
$1^n$ |
$7^n$ |
$3^n$ |
$8^n$ |
$2^n$ |
$6^n$ |
$4^n$ |
| 1 |
9 |
1 |
7 |
3 |
8 |
2 |
6 |
4 |
| 2 |
1 |
1 |
9 |
9 |
4 |
4 |
6 |
6 |
| 3 |
9 |
1 |
3 |
7 |
2 |
8 |
6 |
4 |
| 4 |
1 |
1 |
1 |
1 |
6 |
6 |
6 |
6 |
| 5 |
9 |
1 |
7 |
3 |
8 |
2 |
6 |
4 |
and so on -- the table repeats every 4 rows.
1) $9^{2m+1}+1^{2m+1}(\mbox{mod } 10)=9+1=10$ so must be a multiple
of $10$ $7^{2m+1}+3^{2m+1}(\mbox{mod }10)=7+3$ or $3+7=10$ so must
be a multiple of $10$
3) $9^{2m}-1^{2m}(\mbox{mod }10)=1-1=0$ so must be a multiple of
$10$
$7^{2m}-3^{2m}(\mbox{mod }10)=1-1$ or 9-9=0 so must be a multiple
of 10
2) $8^{2m}-2^{2m}(\mbox{mod }10)=4-4$ or $6-6=0$ so must be a
multiple of $10$
$6^{2m}-4^{2m}(\mbox{mod }10)=6-6=0$ so must be a multiple of
10
4) $8^{2m+1}+2^{2m+1}(\mbox{mod }10)=8+2$ or $2+8=10$ so must be a
multiple of $10$
$6^{2m+1}+4^{2m+1}(\mbox{mod }10)=6+4=10$ so must be a multiple of
$10$.
So all are multiples of $10$.
Mark (no school given) wrote up a lovely
solution using two methods: first he looked at the properties of
the units digit in the sums and then looked at the implications of
the binomial theorem. His solution was beautifully written up in
Word, so we attach a full pdf version of
his work. It is well worth a read!
Babu (no school given) proved for first part using the binomial
theorem:
Consider the power $n$ as an odd number, say $2m+1$, so that we
need to prove that $7^{2m+1} + 3^{2m+1}$ is a multiple of $10$
always.
$$
7^{2m+1} + 3^{2m+1}= (10 - 3)^{2m+1} + 3^{2m+1}
$$
On expanding the right hand side of the above equation using
binomial theorem we get,
$$
10^{2m+1} + _{2m+1}C_1 \times 10^{2m} \times (-3)^1 +
_{2m+1}C_2 \times 10^{2m+1} \times (-3)^2+ \cdots +(-3)^{2m+1}
+ 3^{2m+1}$$
By cancelling the last two terms, we see that all remaining terms
have a factor of $10$. Hence the sum is also a multiple of $10$.
By trial and error we can see that the result is not necessarily
true for even powers.
Patrick Stevens from Woodbridge school and
Robert from The King's School, Grantham both gave the clear proofs
starting directly from the moular form of the
equations.
For part 1, Robert wrote:
Let $n=2x+1$, where $x\in\mathbb{Z}$ Then $$ \begin{eqnarray}
9^n+1^n &=& 9^{2x+1}+1^{2x+1}\cr &=& (9^2)^x\times
9 +1 \cr 9&\equiv& 9\pmod{10}\cr 9^2&\equiv&
81\pmod{10}\equiv 1\pmod{10} \end{eqnarray} $$ $$ \begin{eqnarray}
\therefore 9^n+1^n&\equiv&\left(1\pmod{10}\right)^x\times
9\pmod{10}+1\pmod{10}\cr &\equiv& \left(1\times 9
+1\right)\pmod{10}\cr &\equiv& 10 \pmod{10} \cr
&\equiv& 0\pmod{10}\quad\quad\mbox{QED} \end{eqnarray} $$
Robert then proceeded to prove the other
three parts in this way.
Patrick constructed some great modular
arithmetic answers. For part 2, for example, he wrote:
$8^{n}\equiv (-2)^n\pmod{10}$ so $8^n-2^n\equiv (-2)^n
-2^n\pmod{10}$. Since for even $n$ we have $(-2)^n =
(2)^n\pmod{10}$ we have $(-2)^n-2^n \equiv 0 \pmod{10}$; this,
therefore, is divisible by $10$.
We liked this approach of Patrick's because
from this it is easy to spot generalisations, along with the
algebra that backs them up. Patrick continued by
saying:
Let us take $x = 0$ to $9$, without losing generality, since any
natural number is congruent to one of these numbers in modulo $10$.
Therefore, generalising the first equation we get
$$
x^n + (10-x)^n (\mbox{mod } 10) \equiv x^n + (-x)^n\equiv
x^n(1 + (-1)^n)
$$
Therefore, if $n$ is odd, then we have $x^n(1-1) = 0$, for all
$x$.
We are now left to find a general equation for even $n$. If $n$ is
even, we have $x^n(1+1) = x^n \times 2$. We have only $x = 0,
2, 4, 6, 8$ to worry about here; for $x = 0$, the product will be
$0$ so this is divisible by $10$. Since we have defined $n$ to be
even, then $2^n \equiv (-2)^n$, so in modulo $10$, the result
will be the same for $2$ and $8$, and for $4$ and $6$. We have two
cases left to check, then: $x = 2$ and $x = 4 = 2^2$. Let $x = 2$,
then we have $2^n \times 2 = 2^{n+1}$; for $x = 4$, we have
$(2^2)^n \times 2 \equiv 2^{2n+1}$. Neither of these will ever be
divisible by $10$, since in order to have $10$ as a factor, the
number must have a factor of $5$; but it has just been proved that
these numbers will only be divisible by $2$. Therefore, $x^n +
(10-x)^n$ is always divisible by $10$, except when $n = -2, 2,
-4, 4$ in modulo $10$.
Generalising the second equation,
$$
x^n - (10-x)^n (\mbox{mod }10) \equiv x^n - (-x)^n(\mbox{mod
}10)
$$
For all even $n$, $(-x)^n = x^n$, so $x^n - (-x)^n = x^n - x^n = 0
(\mbox{ mod} 10)$. For odd $n$, we have $x^n + x^n = 2\times x^n$;
this therefore looks like it can't be generalised.
There are at least three methods of proving the results that for
odd values of $n$, $9^n + 1^n$, $8^n + 2^n$, $7^n + 3^n$ and $6^n +
4^n$ are multiples of $10 $ whereas, if $n$ is even, then $9^n -
1^n$, $8^n - 2^n$, $7^n - 3^n$ and $6^n - 4^n$ are multiples of
$10$.
These results can be proved using the axiom
of mathematical induction but a simpler approach is to use the
periodicity of the values of the last digit for powers of integers.
Emma from St Paul's Girls' School and Andrei from Tudor Vianu
National College, Bucharest, Romania both used this method of
solution. As Andrei tabulated his results his solution is
shorter:
Proof using the periodicity of
last digits of powers of integers and Modular arithmetic
I shall determine the last digit of each of the numbers: $1^n$,
$2^n$, $3^n$, $4^n$, $6^n$, $7^n$, $8^n$, $9^n$. The last digit of
$1^n$ is always 1, and for $6^n$ it is always $6$. For $2$, $3$,
$7$ and $8$ the last digit of their powers repeats with periodicity
$4$, as shown in the table:
| $n \pmod 4$ |
$0$ |
$1$ |
$2$ |
$3$ |
| $2$ |
$6$ |
$2$ |
$4$ |
$8$ |
| $3$ |
$1$ |
$3$ |
$9$ |
$7$ |
| $7$ |
$1$ |
$7$ |
$9$ |
$3$ |
| $8$ |
$6$ |
$8$ |
$4$ |
$2$ |
For $4$ and $9$, the last digit of their powers repeats with
periodicity $2$:
| $n \pmod 2$ |
$0$ |
$1$ |
| $4$ |
$6$ |
$4$ |
| $9$ |
$1$ |
$9$ |
Having creating these tables, I shall prove the required
results:
(1) If $n$ is odd, the last digit of $9^n$ is 9, and as the
last digit of $1^n$ is always $1$, so the the last digit of $9^n +
1^n$ is $0$, and the number is a multiple of $10$.
For $7^n + 3^n$ there are two possible cases: $n =
1\pmod{4}$.
Here $7^n + 3^n = (7 + 3)\pmod{10}= 0\pmod{10}$ $n =
3\pmod{4}$. Here $7^n + 3^n = (3 + 7)\pmod{10} = 0\pmod{10}$
(2) If $n$ is even it is very easy to look in the table above
to obtain the desired results.
First I look at $8^n - 2^n$ for different values of $n$ -
even. If $n = 2\pmod{4}$, then $8^n - 2^n = (4-4) \pmod{10} =
0\pmod{10}$.
If $n = 0\pmod{4}$, $8^n - 2^n = (6-6) \pmod{10} = 0 \pmod
{10}$.
For, $6^n - 4^n$, I also obtain $(6-6) \pmod{10} = 0
\pmod{10}$.
(3) If $n$ is even: $9^n - 1^n$ is a multiple of $10$. The
proof derives evidently from the table. In a similar manner, $7^n -
3^n$ is also a multiple of $10$.
(4) If $n$ odd: $8^n + 2^n$ and $6^n + 4^n$ are both multiples
of $10$.
Sam from SAC (Malta) made a very clear
conjecture related to this problem:
I noticed that both $9 + 1$ and $7 + 3$ add up to $10$, so
a conjecture for odd numbers is:
$(a + b)$ is a factor of $(a^n + b^n)$
where $a$ and $b$ are any constants and $n \in \{\mbox{odd
numbers}\}$.
Furthermore, both $8+2$ and $6+4$ add up to $10$, so
a conjecture for even numbers is
$(a + b)$ is a factor of $(a^n- b^n)$, where $a$ and $b$ are any
constants and $n \in\{\mbox{even numbers}\}$
Note here that both {odd numbers} and {even numbers} are subsets of
$\mathbb{N}$. Combining these conjectures I got: $(a + b)$ is a
factor of $(a^n + (-1)^{n-1} b^n)$, where $a$ and $b$ are any
constants and $n \in \mathbb{N}$.
Sam managed to prove this by
induction
Let
$$
\begin{eqnarray}
f(k)&=&a^k + (-1)^{k-1} b^k\cr
f(k+1)&=&a^{k+1} + (-1)^k b^{k+1}
\end{eqnarray}
$$
$f(k+1)$
can also be expressed as
$$
\begin{eqnarray}
f(k+1)&=&a^{k+1}+(-1)^{k-1} ab^k - (-1)^{k-1} ab^k+ (-1)^k
b^{k+1}\cr
&=&a(a^k+ (-1)^{k-1} b^k )- (-1)^{k-1} b^k
(a-(-1)b)\cr
&=&af(k)+ (-b)^k (a+b)
\end{eqnarray}
$$
Therefore, $(a + b)$ is a factor of $f(k + 1)$ if it is a factor of
$f(k)$. Using $k = 1: f(1)= a+b$ Therefore, $(a + b)$ is a factor
of $f(k)$ when $k = 1$, so $(a + b)$ is a factor of $f(k+1)$, and
so on for all natural numbers $k$.
Alternative
Methods
(1) We want to prove for all odd integers $n> 0$ the statement
$P(n)$ that $9^n + 1^n$ is a multiple of 10. $P(1)$ is true.
If $P(k)$ is true then consider $P(k+2)$: $$9^{k+2} + 1^{k+2} =
81(9^k + 1^k)-80$$ so $P(k+2)$ is true and the result is true for
all odd numbers by the axiom of induction.
Similarly $7^1 + 3^1$ is a multiple of 10 and if $7^k + 3^k$ is a
multiple of 10 then $$7^{k+2} + 3^{k+2} = 49(7^k) + 9(3^k) =
40(7^k) + 9(7^k + 3^k)$$ so this is also a multiple of 10 and the
result is true for all odd numbers by the axiom of induction. Note
that $9^2+1^2$ and $7^2+3^2$ are not multiples of 10 so the result
is not true for even numbers.
(2) We have $8^0-2^0$ and $8^2-2^2$ are both multiples of 10. If
$8^k-2^k$ is a multiple of 10 then $$8^{k+2} - 2^{k+2} = 64(8^k) -
4(2^k) = 60(8^k) +4(8^k-2^k)$$ so this is a multiple of 10 and the
result is true for all even numbers. Similarly $6^2-4^2$ is a
multiple of 10 and if $6^k-4^k$ is a multiple of 10 then $$6^{k+2}
- 4^{k+2}= 36(6^k) - 16(4^k) = 20(6^k) + 16(6^k-4^k)$$ which is a
multiple of 10 and so the result is true for all even
numbers.
Note that $8 - 2$ and $6 - 4$ are not multiples of 10 and the
result is not true for odd powers.
(3) The corresponding results are $9^n - 1^n$ and $7^n - 3^n$ are
multiples of 10 when $n$ is an even number which can be proved by
induction.
(4) Similarly $8^n + 2^n$ and $6^n + 4^n$ are multiples of 10 when
$n$ is an odd number which can be proved by induction.
Proof using the Binomial
Theorem
$$7^n + 3^n = 7^n + (10-7)^n = 7^n + 10^n + ..... + (-7)^n.$$ All
the terms of the Binomial expansion involve powers of 10 apart from
the term $(-7)^n$ so the expression is a multiple of 10 when $n$ is
odd but not when $n$ is even. The same method works for all other
parts of the question.