# Difference between revisions of "2009 IMO Problems/Problem 1"

m |
(→Solution 2) |
||

(2 intermediate revisions by the same user not shown) | |||

Line 9: | Line 9: | ||

Let <math>n=pq</math> such that <math>p\mid a_1</math> and <math>q\mid a_2-1</math>. Suppose <math>n</math> divides <math>a_k(a_1-1)</math>. | Let <math>n=pq</math> such that <math>p\mid a_1</math> and <math>q\mid a_2-1</math>. Suppose <math>n</math> divides <math>a_k(a_1-1)</math>. | ||

Note <math>q\mid a_2-1</math> implies <math>(q,a_2)=1</math> and hence <math>q\mid a_3-1</math>. Similarly one has <math>q\mid a_i-1</math> for all <math>i</math>'s, in particular, <math>p\mid a_1</math> and <math>q\mid a_1-1</math> force <math>(p,q)=1</math>. Now <math>(p,a_1-1)=1</math> gives <math>p\mid a_k</math>, similarly one has <math>p\mid a_i</math> for all <math>i</math>'s, that is <math>a_i</math>'s satisfy <math>p\mid a_i</math> and <math>q\mid a_i-1</math>, but there should be at most one such integer satisfies them within the range of <math>1,2,\ldots,n</math> for <math>n=pq</math> and <math>(p,q)=1</math>. A contradiction!!! | Note <math>q\mid a_2-1</math> implies <math>(q,a_2)=1</math> and hence <math>q\mid a_3-1</math>. Similarly one has <math>q\mid a_i-1</math> for all <math>i</math>'s, in particular, <math>p\mid a_1</math> and <math>q\mid a_1-1</math> force <math>(p,q)=1</math>. Now <math>(p,a_1-1)=1</math> gives <math>p\mid a_k</math>, similarly one has <math>p\mid a_i</math> for all <math>i</math>'s, that is <math>a_i</math>'s satisfy <math>p\mid a_i</math> and <math>q\mid a_i-1</math>, but there should be at most one such integer satisfies them within the range of <math>1,2,\ldots,n</math> for <math>n=pq</math> and <math>(p,q)=1</math>. A contradiction!!! | ||

+ | |||

+ | == 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>, 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 \mid 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. |

## Latest 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.