nr 1 altijd doenbaar
Opgave - IMO 2009 dag 1 vraag 1
Zij $n \in \mathbb{N}$ en $a_1,a_2,\cdots,a_k$ $k\ge 2$ verschillende getallen uit $\{1,2\cdots,n\}$ zijn zodat $n|a_i(a_{i+1}-1)$ $\forall i \in \{1,2,\cdots, k-1\}$ .
Bewijs dat $n \not|a_k (a_1 -1).$
- login om te reageren
Oplossing
We hebben uit de gegevens dat $$\prod_{i=1}^ka_i\equiv a_1\mod n$$ door herhaaldelijk $a_{i+1}a_i\equiv a_i \mod{n}$ toe te passen
Veronderstel nu dat $a_ka_1\equiv a_k \mod{n}$. Dan is $$\prod_{i=1}^ka_i\equiv \prod_{i=2}^ka_i\equiv a_2\mod{n}$$ waardoor $a_1\equiv a_2$, maar alle $a_i$ zijn verschillend en er geldt $0 < a_i\leq n$. Contradictie.