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

(→Problem) |
(→Solution) |
||

Line 11: | Line 11: | ||

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!!! | ||

− | |||

− |

## Revision as of 06:23, 23 July 2009

## 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*

--Bugi 10:23, 23 July 2009 (UTC)Bugi

## 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!!!