# 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 21: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.