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