1971 Canadian MO Problems/Problem 6
Problem
Show that, for all integers ,
is not a multiple of
.
Solutions
Solution 1
. Consider this equation mod 11.
.
The quadratic residues
are
, and
(as shown below).
If ,
, thus not a multiple of 11, nor 121.
If ,
, thus not a multiple of 11, nor 121.
If ,
, thus not a multiple of 11, nor 121.
If ,
, thus not a multiple of 11, nor 121.
If ,
, thus not a multiple of 11, nor 121.
If ,
, thus not a multiple of 11, nor 121.
If ,
, thus not a multiple of 11, nor 121.
If ,
, thus not a multiple of 11, nor 121.
If ,
, thus not a multiple of 11, nor 121.
If ,
, thus not a multiple of 11, nor 121.
If ,
. However, considering the equation
for
, testing
, we see that
always leave a remainder of greater than
.
Thus, for any integer ,
is not a multiple of
.
Solution 2
, so if this is a multiple of 11 then
is too. Since 11 is prime,
must be divisible by 11, and hence
is divisible by 121. This shows that
can never be divisible by 121.
See Also
1971 Canadian MO (Problems) | ||
Preceded by Problem 5 |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • | Followed by Problem 7 |