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

Latest revision as of 16:41, 27 July 2025

Problem

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

Author: Ross Atkins, Australia

Solution

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

Solution 2

Let $n = p_1^{b_1}p_2^{b_2} \cdots p_s^{b_s}$ . Then after toying around with the $p_i^{b_i}$ and what they divide, we have that $p_i^{b_i} \nmid a_k$ , and so in particular, $n \nmid a_k$ .

Assume by way of contradiction that $n \mid a_k(a_1 - 1)$ . Then $n \mid a_1 - 1$ . Now we shift our view towards the $a_i(a_{i + 1} - 1)$ . Here each $p_i^{b_i}$ divides $a_i(a_{i + 1} - 1) \implies a_ia_{i + 1} \equiv a_i \pmod{p_i^{b_i}}$ . Hence we have the chain of equivalences $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}}$ . Now we also have that $p_i^{b_i} \mid n \mid a_1 - 1$ . Thus $a_1 \equiv 1 \pmod{p_i^{b_i}}$ . Now plugging this value of $a_1$ modulo $p_i^{b_i}$ , we obtain that $a_1 \equiv a_2 \equiv a_3 \equiv \cdots a_k \equiv 1 \pmod{p_i^{b_i}}$ . Hence this chain of congruences is also true for $n$ as $p_i$ was arbitrary. However as all the $a_i \in \{1, 2, \dots, n\}$ we have that not all the $a_i$ are distinct, and so this is a contradiction.

Solution 3

Suppose by contradiction that $n=pq$ and $n | a_k(a_1-1)$ such that $p | a_1 -1$ and $q | a_k$ . Since $(p,a_1) = 1$ , but $pq | a_1(a_2-1)$ one has $p|a_2-1$ . Furthermore by induction $p|a_k-1$ . Similarly since $(q,a_k-1)=1$ , but $pq | a_{k-1}(a_k-1)$ one has $q | a_{k-1}$ . By induction $q| a_1$ . We've shown $n=pq | a_1(a_k-1)$ Therefore $n | a_1(a_k-1) - a_k(a_1-1) = a_k-a_1$ which is impossible since $0< |a_k-a_1| < n$ .

~not_detriti

@@ Line 4: / Line 4: @@
 ''Author: Ross Atkins, Australia''
---[[User:Bugi|Bugi]] 10:23, 23 July 2009 (UTC)Bugi
 == Solution ==
@@ Line 11: / 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>.
 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.
+== Solution 3 ==
+Suppose by contradiction that <math>n=pq</math> and <math>n | a_k(a_1-1)</math> such that <math>p | a_1 -1</math> and <math>q | a_k</math>. Since <math>(p,a_1) = 1</math>, but <math>pq | a_1(a_2-1)</math> one has <math>p|a_2-1</math>. Furthermore by induction <math>p|a_k-1</math>. Similarly since <math>(q,a_k-1)=1</math>, but <math>pq | a_{k-1}(a_k-1)</math> one has <math>q | a_{k-1}</math>. By induction <math>q| a_1</math>. We've shown
+<cmath>
+n=pq | a_1(a_k-1)
+</cmath>
+Therefore <math>n | a_1(a_k-1) - a_k(a_1-1) = a_k-a_1</math> which is impossible since <math>0< |a_k-a_1| < n</math>.
+~not_detriti
+==See Also==
+{{IMO box|year=2009|before=First Problem|num-a=2}}

2009 IMO (Problems) • Resources
Preceded by First Problem	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 2
All IMO Problems and Solutions

Page

Toolbox

Search