IMO 2009, Problem 1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3647 posts

orl

#1 h Jul 15, 2009, 2:26 PM • 18 Y

Y by Amir Hossein, Davi-8191, Vietjung, palindrome868, Aritra12, itslumi, jhu08, megarnie, Adventure10, Mango247, Tellocan, ItsBesi, and 6 other users

Let $n$ be a positive integer and let $a_1,a_2,a_3,\ldots,a_k$ $( k\ge 2)$ be distinct integers in the set ${ 1,2,\ldots,n}$ such that $n$ divides $a_i(a_{i + 1} - 1)$ for $i = 1,2,\ldots,k - 1$ . Prove that $n$ does not divide $a_k(a_1 - 1).$

Proposed by Ross Atkins, Australia

This post has been edited 2 times. Last edited by orl, Jul 15, 2009, 11:08 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ychjae

53 posts

ychjae

#2 h Jul 15, 2009, 2:43 PM • 12 Y

Y by TheWalkingD, kirillnaval, Supermathlet_04, jhu08, megarnie, ericxyzhu, Adventure10, Mango247, and 4 other users

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Erken

1363 posts

Erken

#3 h Jul 15, 2009, 2:45 PM • 33 Y

Y by zaurimeshveliani, rightways, MSTang, tenplusten, div5252, JasperL, Supercali, amar_04, Smkh, Supermathlet_04, Illuzion, jhu08, ZHEKSHEN, megarnie, 507219, rama1728, jrsbr, levifb, Schur-Schwartz, Adventure10, Mango247, Tellocan, Lincito_31, Carius_MrPenguin, EpicBird08, farhad.fritl, and 7 other users

too easy no?

$a_1\equiv a_1\cdot a_2\equiv a_1\cdot a_2\cdot a_3\equiv \dots \equiv a_1\cdot\dots\cdot a_k\equiv a_1\cdot\dots\cdot a_{k - 2}\cdot a_k\equiv\dots\equiv a_1\cdot a_{k}\equiv a_k$ .

Therefore, $0 < |a_1 - a_k| < n$ is divisible by $n$ . Contradiction.

P.S Please add 's' in the statement, integers

This post has been edited 3 times. Last edited by Erken, Jul 15, 2009, 3:35 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

TomciO

552 posts

TomciO

#4 h Jul 15, 2009, 2:50 PM • 9 Y

Y by Abdollahpour, Supermathlet_04, jhu08, Adventure10, Mango247, and 4 other users

We prove inductively that $n|a_1a_l - a_1$ for $l=2, 3, \ldots, k$ . We know that it's true for $l=2$ . Suppose that it's true for $l$ . Since $n|a_1a_l-a_1$ and $n|a_la_{l+1} - a_l$ we know that also $n|(a_1a_l-a_1)a_{l+1} - a_1a_l+a_1$ and $n|a_1a_la_{l+1} - a_1a_l$ . Substracting gives exactly what we want and the induction proof is complete.
Since $n|a_1a_k - a_1$ we can't have $n|a_k(a_1-1)=a_ka_1 - a_k$ since it would imply $n|a_1-a_k$ , which is impossible.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Bugi

1857 posts

Bugi

#5 h Jul 15, 2009, 3:04 PM • 4 Y

Y by jhu08, Adventure10, Mango247, and 1 other user

It is an easy problem!!! I solved it!!! It's very similar to ychjae's, but I complicated stuff with prime factors of n...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pbornsztein

3004 posts

pbornsztein

#6 h Jul 15, 2009, 3:11 PM • 5 Y

Y by jhu08, Adventure10, Mango247, and 2 other users

Another wording for the same approach : all equalities are considered modulo $n$ .
We know that $a_{i+1}a_i = a_i$ for all $i \leq k-1$ , thus clearly $a_ia_{i-1} \cdots a_1 = a_1$ for all $i \leq k$ .
But, leaving $a_i$ , this also gives $a_i(a_{i-1} \cdots a_1) = a_ia_1$ for all $i \leq k$ .

It follows that $a_ka_1 = a_1$ .
Since $k \geq 2$ and $a_k,a_1$ belong to $\{1, \cdots , n \}$ we cannot have $a_k = a_1$ , thus $a_ka_1 \neq a_k$ , as desired.

Pierre.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jgnr

1343 posts

jgnr

#7 h Jul 15, 2009, 3:13 PM • 4 Y

Y by jhu08, Adventure10, Mango247, and 1 other user

too easy I think, it only took me 15 minutes. my approach is similar to ychjae's. i used chinese remainder theorem.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lambruscokid

264 posts

lambruscokid

#8 h Jul 15, 2009, 3:25 PM • 3 Y

Y by jhu08, Adventure10, Mango247

Same solution as ychjae, but to finish the problem I used chinese remainder theorem as well as johan

I think it is simple, yet very nice problem

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

apratimgtr

81 posts

apratimgtr

#9 h Jul 15, 2009, 3:53 PM • 4 Y

Y by jhu08, Adventure10, Mango247, and 1 other user

Suppose the contrary is true.Then we have $n^{k} |\prod^{k}_{i = 1} a_{i}(a_{i}-1)$ which imply
there exist j such that $n|a_{j}(a_{j} - 1)$ Then by considering two cases $"n|a_{j}"$ and $"n|a_{j } - 1"$ we have $a_{j} = a_{j - 1}$ or $a_{j} = a_{j + 1}$ .A contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cocoowner

28 posts

cocoowner

#10 h Jul 15, 2009, 4:26 PM • 3 Y

Y by jhu08, Adventure10, Mango247

There is a simple method to prove the last.
$p|a_{i} -a_{i+1}$ , $q|(a_{i}-1)-(a_{i+1}-1)$ , so $pq|a_{i} -a_{i+1}$ . A Contradiction!!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

trigg

36 posts

trigg

#11 h Jul 15, 2009, 4:43 PM • 4 Y

Y by jhu08, Adventure10, Mango247, and 1 other user

I solved it in the exam from this way:
clearly a1=a1.a2 (mod n) then a1.a3=a1.a2.a3 (mod n) and from a2.a3=a2 (mod n) we have a1=a1.a2=a1.a3 (mod n) and we have from the same way a1=a1.a2=a1.a3=...=a1.ak (mod n) so a1=a1.ak (mod n) (*)
For the sake of contradiction we may assume that ak=a1.ak (mod n) then we have a1=ak (mod n) from (*) ,contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

uglysolutions

304 posts

uglysolutions

#12 h Jul 15, 2009, 5:05 PM • 4 Y

Y by jhu08, Adventure10, Mango247, and 1 other user

Suppose $n|a_k(a_1 - 1)$ .

If $\gcd (a_1,n) = 1$ , we have $n|a_2-1$ , then $\gcd (a_2,n) = 1$ and so $n|a_3 - 1 \rightarrow a_2 = a_3$ , a contradiction.
If $\gcd (a_1,n) = n$ , we have $\gcd (a_1-1,n)=1$ , hence $n|a_k \rightarrow a_1=a_k=n$ , contradiction again.

Now, we know that $1 < \gcd (a_1,n) < n$ . This means that there is a prime $p$ such that $p$ divides both $a_1$ and $n$ , yet the exponent of $p$ in the prime factorization of $a_1$ is less than the exponent of $p$ in the prime factorization of $n$ .

Hence, $p|a_2-1$ . But then $p$ does not divide $a_2$ , so $p|a_3-1$ , and so on, until we get $p|a_1-1$ , which is absurd because we said $p|a_1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Erken

1363 posts

Erken

#13 h Jul 15, 2009, 5:06 PM • 3 Y

Y by jhu08, Adventure10, Mango247

uglysolutions

why $p$ divides $a_2-1$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

uglysolutions

304 posts

uglysolutions

#14 h Jul 15, 2009, 5:22 PM • 3 Y

Y by jhu08, Adventure10, Mango247

Because $n|a_1(a_2 - 1)$ and the exponent of $p$ in the prime factorization of $a_1$ is less than the exponent of $p$ in the prime factorization of $n$ , hence there must be at least one more $p$ factor in $a_2 - 1$ .

I mean, if $p^{\alpha}||n$ and $p^{\beta}||a_1$ , we have $p^{\alpha - \beta}|a_2 - 1$ , since $\alpha > \beta \rightarrow \alpha - \beta \geq 1$ we can say $p|a_2 - 1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

keira_khtn

485 posts

keira_khtn

#15 h Jul 15, 2009, 5:33 PM • 2 Y

Y by jhu08, Adventure10

Easy but very good one.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lnzhonglp

120 posts

lnzhonglp

#134 h Jun 23, 2024, 6:28 AM

Y by

Assume FTSOC that $n$ divides $a_k(a_1-1)$ . Then, taking indices modulo $k$ , the condition implies that $a_i \equiv a_ia_{i+1} \pmod n$ for all $i$ . Then we have
$a_1 \equiv a_1a_2 \equiv a_1a_2a_3 \equiv \dots \equiv a_1a_2\dots a_k \equiv a_2a_3 \dots a_k \equiv a_2a_3 \dots a_{k+1}\equiv \dots \equiv a_2 \pmod n,$ so $a_1 = a_2$ , contradiction. Therefore, $n \nmid a_k(a_1-1)$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ProMaskedVictor

43 posts

ProMaskedVictor

#135 h Jul 22, 2024, 11:43 AM

Y by

$a_1a_2 \equiv a_1 \pmod n$ .
$a_2a_3 \equiv a_2 \pmod n \implies a_1a_2a_3 \equiv a_1a_2 \equiv a_1 \pmod n$
Again, $a_1a_2 \equiv a_1\pmod n \implies a_1a_2a_3 \equiv a_1a_3 \pmod n$ .
So, $a_1a_3 \equiv a_1 \pmod n$ .
Continuing this process, we can easily say that $a_1a_k\equiv a_1\pmod n$ .
So, $a_k(a_1-1)\equiv a_k-a_1 \pmod n.$
Now, $0<|a_k-a_1|<n$ as $a_i \in \{1,2,\cdots n\}\; \forall \;i\in\{1,2,\cdots,k\}$ .
So, $\boxed{n \nmid a_k(a_1-1)}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

EpicBird08

1751 posts

EpicBird08

#136 h Jul 27, 2024, 2:41 AM

Y by

Assume for the sake of contradiction that $n$ divided all of $a_i(a_{i+1} - 1)$ , taking indices modulo $n.$ Extend $a_i$ such that $a_{n+i} = a_i$ for all $i.$
Claim: $a_i a_{i+1} \dots a_{i+k} \equiv a_i \pmod{n}$ for all positive $i$ and nonnegative $k.$
Proof: By induction on $k.$ The base case $k=0$ is obvious, and for the inductive step, assume that this holds for a certain $k$ and all positive $i.$ Then $a_{i+1} \dots a_{i+k+1} \equiv a_{i+1} \pmod{n},$ so multiplying both sides by $a_i$ gives $a_i a_{i+1} \dots a_{i+k+1} \equiv a_i a_{i+1} \equiv a_i \pmod{n}$ by the problem condition, so our induction is complete.
In particular, taking $k = n-1,$ we get that $a_1 \dots a_n \equiv a_1 \equiv a_2 \equiv \dots \equiv a_n \pmod{n},$ contradiction since all the $a_i$ are distinct.

This post has been edited 2 times. Last edited by EpicBird08, Jul 27, 2024, 2:41 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Sagnik123Biswas

420 posts

Sagnik123Biswas

#137 h Aug 23, 2024, 8:19 AM

Y by

Sketch: Try a proof by contradiction. We will see that $a_ia_{i+1} \equiv a_1a_2a_3 \dots a_k \pmod{n}$ . From here, it follows that $a_1 \equiv a_2 \equiv a_3 \dots \equiv a_k \pmod{n}$ which is a contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ezpotd

1263 posts

ezpotd

#138 h Aug 31, 2024, 5:13 PM

Y by

Assume that this is possible, we force a contradiction. First, clearly observe $a_i$ can never be $n$ , because then we would have $n \mid a_{i - 1}(a_{i} - 1)$ (indices taken modulo $k$ since assuming that $n \mid a_k (a_1 - 1)$ means that $n \mid a_i (a_{i + 1} - 1)$ for all $i$ ), which is clearly forces $a_{i - 1}$ , violating the distinct condition. Take some arbitrary index $i$ . Now there exist integers $p, q > 1$ such that $pq = n, p \mid a_{i}, q \mid a_{i + 1} - 1$ . Now since $\gcd(p, a_i - 1) = 1$ , and $p \mid a_{i - 1} (a_i - 1)$ , we have $p \mid a_{i - 1}$ . Repeating this logic, we have $p \mid a_{i}$ for all $i$ . Likewise, we can show $q \mid a_{i + 1} - 1$ for all $i$ . Now if $p,q$ share a common factor, we have an obvious contradiction since this common factor divides $a_i$ and $a_i - 1$ . If they don't we can use $CRT$ to show all $a_i$ are congruent mod $n$ , which is a contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jc.

11 posts

jc.

#139 h Sep 9, 2024, 12:59 PM • 1 Y

Y by MihaiT

let us assume to the contrary that $n \mid a_k(a_1-1)$ that is $a_ka_1 \equiv a_k \pmod n$ . now since $n$ divides $a_i(a_{i+1} - 1)$ for $i = 1,2,\dots,k-1$ , we have

$a_1a_2 \equiv a_1 \pmod n$ $a_1a_2a_k \equiv a_1a_k \pmod n$ $a_2a_k \equiv a_k \pmod n$ and similarly
$a_2a_3 \equiv a_2 \pmod n$ $a_2a_3a_k \equiv a_2a_k \pmod n$ $a_3a_k \equiv a_k \pmod n$ and so on we get $a_{k-1}a_k \equiv a_k \pmod n$ , but we also have $a_{k-1}a_k \equiv a_{k-1} \pmod n$ . This implies
$a_{k-1} \equiv a_k \pmod n$ but both $a_{k-1}$ and $a_k$ are distinct integers $\leq n$ , which is not true, thus our initial assumption i.e. $n$ divides $a_i(a_{i+1} - 1)$ is false

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

doulai1

597 posts

doulai1

#140 h Oct 2, 2024, 3:12 PM

Y by

Redacted

This post has been edited 4 times. Last edited by doulai1, Feb 7, 2025, 4:00 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

megahertz13

3183 posts

megahertz13

#141 h Nov 17, 2024, 1:54 AM

Y by

Assume otherwise. We have $a_1(a_2-1)\equiv 0\pmod n$ $a_2(a_3-1)\equiv 0\pmod n$ $a_3(a_4-1)\equiv 0\pmod n$ $\dots$ $a_{k-1}(a_{k}-1)\equiv 0\pmod n$ $a_{k}(a_{1}-1)\equiv 0\pmod n.$ Let $q=p^e$ be any prime power dividing $n$ . Note that we have $a_1\equiv 0\pmod q$ or $a_{i+1}\equiv 1\pmod q.$
If $a_1\equiv 0\pmod q$ , we have $a-1\ne 1\pmod q$ , so $a_k\equiv 0\pmod q$ . Repeating this argument gives $a_i\pmod q$ constant.

If $a_2\equiv 1\pmod q$ , we have $a_2\ne 0\pmod q$ , so $a_3\equiv 1\pmod q$ . Repeating this argument gives $a_i\pmod q$ constant.

By the Chinese Remainder Theorem, we have $a_i\pmod n$ constant. However, this finishes.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AshAuktober

1005 posts

AshAuktober

#142 h Nov 17, 2024, 4:58 AM

Y by

Key idea: break into prime powers and do divisibility stuff, then combine using CRT.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SimplisticFormulas

114 posts

SimplisticFormulas

#143 h Nov 17, 2024, 7:04 AM • 1 Y

Y by MihaiT

Slick question.
Let $n= p_{1}^{a_{1}}\cdot p_{2}^{a_{2}} \cdot … \cdot p_{l}^{a_{l}}$ is the unique prime factorization of $n$ .
Assume that for some $1 \le j \le k$ , $j \in \mathbb{N}$ ,
$p_{s} \mid a_{j}-1$ , where $p_{s}$ is a prime factor of $n$ . Then
$p_{s} \nmid a_{j} \implies p_{s}^{a_{s}} \mid a_{j+1}-1$ , $\forall 1\le s \le l$
$\implies a_{j+1}-1 \ge p_{1}^{a_{1}}\cdot p_{2}^{a_{2}} \cdot … \cdot p_{l}^{a_{l}}=n$ , which is a contradiction since $\{a_{1},a_{2},…,a_{k}\} \in \{1,2,…,n\}$ .
Hence, $p_{s}^{a_{s}} \mid a_{j-1}$ , which again gives
$\implies a_{j-1} \ge p_{1}^{a_{1}}\cdot p_{2}^{a_{2}} \cdot … \cdot p_{l}^{a_{l}}=n$ , $\forall$ $1\le j\le k$ , another contradiction. $\blacksquare$

edit: my proof implies that such a set up cannot even exist irrespective of whether $n \mid a_{1}(a_{k}-1)$ or not. Is it correct? I cannot find any mistake.

This post has been edited 1 time. Last edited by SimplisticFormulas, Nov 17, 2024, 8:39 AM
Reason: mistake

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Maximilian113

575 posts

Maximilian113

#144 h Nov 18, 2024, 9:57 PM

Y by

FTSOC assume otherwise. Then $a_k \equiv a_1 a_k \equiv a_1a_2a_k \equiv \cdots \equiv a_1a_2a_3 \cdots a_{k-1}a_k \equiv a_1a_2 \cdots a_{k-1} \equiv \cdots \equiv a_1a_2 \equiv a_1 \pmod n,$ a contradiction. QED

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

abeot

125 posts

abeot

#145 h Dec 29, 2024, 1:50 AM • 1 Y

Y by centslordm

Assume FTSOC that $n \mid a_k(a_1 - 1)$ .

Consider a prime $p \mid n$ . Suppose $p^e \mid n$ but $p^{e+1} \nmid n$ .

Claim: We either have $p^e \mid a_i - 1$ for all $i = 1, 2, \dots, k$ , or we have $p^e \mid a_i$ for all $i = 1, 2, \dots, k$ .

Proof. Note that from the divisibilities, $p \mid a_1 - 1 \implies p^e \mid a_2 - 1 \implies p^e \mid a_3 - 1 \implies \dots \implies p^e \mid a_k - 1$ similarly, $p \mid a_k \implies p^e \mid a_{k-1} \implies p^e \mid a_{k-2} \implies \dots \implies p^e \mid a_1$ obviously since $p \mid a_1 - 1$ and $p^e \mid a_1$ cannot hold simultaneously, then $p \mid a_1 - 1 \implies p \nmid a_k \implies p^e \mid a_1 - 1$ Similarly, $p \mid a_k \implies p \nmid a_1 - 1 \implies p^e \mid a_k$ which establishes the two cases. $\blacksquare$

Then by CRT, this implies that all $a_i$ have the same residue modulo $n$ , which is a clear contradiction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sansgankrsngupta

143 posts

sansgankrsngupta

#146 h Jan 27, 2025, 2:00 PM

Y by

OG! We proceed with contradiction.
FTSOC, Assume that $n$ divides $a_i(a_{i + 1} - 1)$ for $i = 1,2,\ldots,k$
$k \leq n$ .
Consider a prime $p$ dividing $n$ , let $t= v_p(n)$ we have that $p^t$ divides $a_i(a_{i + 1} - 1)$ for $i = 1,2,\ldots,k$
set $i=k$ , $p \mid a_k(a_1 - 1)$
Case 1: $p^t|a_k$
Since $p^t|(a_{k-1})(a_k-1).$ Now, since $p^t|a_k \implies p^t \nmid (a_k-1)$ , hence $p^t|(a_{k-1})$
we continue this similarly till we get that $p^t|a_i$ for all $i = 1 \cdots k$ .

Thus $\prod_{p \mid n}p^{v_p(n)} =n \mid a_i$ for all $i= 1 \cdots k$
But $a_1,a_2$ are distinct and are in the range $[1,n]$ . Since, $n$ divides $a_1,a_2$ hence both must be equal to $n$ . A contradiction!

Case2: $p \nmid a_k$

This means that $p^t \mid a_1-1$ .
Since $p^t|(a_{1})(a_2-1).$ Now, since $p^t|a_1-1 \implies p^t \nmid (a_1)$ , hence $p^t|(a_{2}-1)$
we continue this similarly till we get that $p^t|a_i-1$ for all $i = 1 \cdots k$ .
Thus $\prod_{p \mid n}p^{v_p(n)} =n \mid a_i-1$ for all $i= 1 \cdots k$
But $a_1-1,a_2-1$ are distinct and are in the range $[0,n-1]$ . Since, $n$ divides $a_1-1,a_2-1$ hence both must be equal to $0$ . A contradiction!

Hence we are done!

This post has been edited 1 time. Last edited by sansgankrsngupta, Jan 27, 2025, 2:01 PM
Reason: -

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

L13832

268 posts

L13832

#147 h Jan 29, 2025, 5:10 PM

Y by

headsolve
solution

This post has been edited 1 time. Last edited by L13832, Jan 29, 2025, 5:11 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pi271828

3369 posts

pi271828

#149 h Apr 28, 2025, 7:31 PM

Y by

For contradiction, assume $n \mid a_k(a_1-1)$ . Select a prime $p \mid n$ .

Claim: Either $p \mid a_i -1$ for all $a_i$ or $p \mid a_i$ for all $a_i$ .

Proof. Note that if $p \mid a_i-1$ for one index $i$ , then we obviously must have $p \mid a_{i+1}-1$ , and so on. If this is not true for any index $i$ , then it is obvious to see that we must have $p \mid a_i$ for all $i$ . $\square$

Since $\{a_1, a_2, \dots, a_k\}$ must achieve all residues in $\mathbb{Z}_p$ , we have the desired contradiction.

Z K Y