Difference between revisions of "2009 IMO Problems/Problem 1"
(→Solution) |
(→Solution 2) |
||
| Line 12: | Line 12: | ||
== Solution 2 == | == Solution 2 == | ||
| − | Let <math>n = p_1^{b_1}p_2^{b_2} \cdots p_s^{b_s}</math>. Then after toying around with the <math>p_i^{b_i}</math> and what they divide, we have that <math>p_i^{b_i} \nmid a_k</math>. | + | Let <math>n = p_1^{b_1}p_2^{b_2} \cdots p_s^{b_s}</math>. Then after toying around with the <math>p_i^{b_i}</math> and what they divide, we have that <math>p_i^{b_i} \nmid a_k</math>, and so in particular, <math>n \nmid a_k</math>. |
Assume by way of contradiction that <math>n \mid a_k(a_1 - 1)</math>. Then <math>n \nmid a_1 - 1</math>. Now we shift our view towards the <math>a_i(a_{i + 1} - 1)</math>. Here each <math>p_i^{b_i}</math> divides <math>a_i(a_{i + 1} - 1) \implies a_ia_{i + 1} \equiv a_i \pmod{p_i^{b_i}}</math>. Hence we have the chain of equivalences <math>a_1a_2 \equiv a_1 \pmod{p_i^{b_i}}, a_2a_3 \equiv a_2 \pmod{p_i^{b_i}}, \dots, a_{k - 1}a_k \equiv a_{k - 1} \pmod {p_i^{b_i}}</math>. Now we also have that <math>p_i^{b_i} \mid n \mid a_1 - 1</math>. Thus <math>a_1 \equiv 1 \pmod{p_i^{b_i}}</math>. Now plugging this value of <math>a_1</math> modulo <math>p_i^{b_i}</math>, we obtain that <math>a_1 \equiv a_2 \equiv a_3 \equiv \cdots a_k \equiv 1 \pmod{p_i^{b_i}}</math>. Hence this chain of congruences is also true for <math>n</math> as <math>p_i</math> was arbitrary. However as all the <math>a_i \in \{1, 2, \dots, n\}</math> we have that not all the <math>a_i</math> are distinct, and so this is a contradiction. | Assume by way of contradiction that <math>n \mid a_k(a_1 - 1)</math>. Then <math>n \nmid a_1 - 1</math>. Now we shift our view towards the <math>a_i(a_{i + 1} - 1)</math>. Here each <math>p_i^{b_i}</math> divides <math>a_i(a_{i + 1} - 1) \implies a_ia_{i + 1} \equiv a_i \pmod{p_i^{b_i}}</math>. Hence we have the chain of equivalences <math>a_1a_2 \equiv a_1 \pmod{p_i^{b_i}}, a_2a_3 \equiv a_2 \pmod{p_i^{b_i}}, \dots, a_{k - 1}a_k \equiv a_{k - 1} \pmod {p_i^{b_i}}</math>. Now we also have that <math>p_i^{b_i} \mid n \mid a_1 - 1</math>. Thus <math>a_1 \equiv 1 \pmod{p_i^{b_i}}</math>. Now plugging this value of <math>a_1</math> modulo <math>p_i^{b_i}</math>, we obtain that <math>a_1 \equiv a_2 \equiv a_3 \equiv \cdots a_k \equiv 1 \pmod{p_i^{b_i}}</math>. Hence this chain of congruences is also true for <math>n</math> as <math>p_i</math> was arbitrary. However as all the <math>a_i \in \{1, 2, \dots, n\}</math> we have that not all the <math>a_i</math> are distinct, and so this is a contradiction. | ||
Revision as of 20:28, 5 July 2022
Problem
Let 
be a positive integer and let 
be distinct integers in the set 
such that divides 
for 
. Prove that doesn't divide 
.
Author: Ross Atkins, Australia
Solution
Let 
such that 
and 
. Suppose divides .
Note implies 
and hence 
. Similarly one has 
for all 
's, in particular, and 
force 
. Now 
gives 
, similarly one has 
for all 's, that is 
's satisfy and , but there should be at most one such integer satisfies them within the range of 
for and . A contradiction!!!
Solution 2
Let 
. Then after toying around with the 
and what they divide, we have that 
, and so in particular, 
.
Assume by way of contradiction that 
. Then 
. Now we shift our view towards the 
. Here each divides 
. Hence we have the chain of equivalences 
. Now we also have that 
. Thus 
. Now plugging this value of 
modulo , we obtain that 
. Hence this chain of congruences is also true for as 
was arbitrary. However as all the 
we have that not all the are distinct, and so this is a contradiction.
