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 |