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

(Created page with '== Problem == Let <math>n</math> be a positive integer and let <math>a_1,\ldots,a_k (k\ge2)</math> be distinct integers in the set <math>\{1,\ldots,n\}</math> such that <math>n…') |
(→Problem) |
||

Line 2: | Line 2: | ||

Let <math>n</math> be a positive integer and let <math>a_1,\ldots,a_k (k\ge2)</math> be distinct integers in the set <math>\{1,\ldots,n\}</math> such that <math>n</math> divides <math>a_i(a_{i+1}-1)</math> for <math>i=1,\ldots,k-1</math>. Prove that <math>n</math> doesn't divide <math>a_k(a_1-1)</math>. | Let <math>n</math> be a positive integer and let <math>a_1,\ldots,a_k (k\ge2)</math> be distinct integers in the set <math>\{1,\ldots,n\}</math> such that <math>n</math> divides <math>a_i(a_{i+1}-1)</math> for <math>i=1,\ldots,k-1</math>. Prove that <math>n</math> doesn't divide <math>a_k(a_1-1)</math>. | ||

+ | |||

+ | ''Author: Ross Atkins, Australia'' | ||

+ | |||

+ | == Solution == | ||

+ | |||

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

+ | |||

+ | ''Solution by ychjae'' |

## Revision as of 06:14, 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*

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