Točno
2. svibnja 2012. 13:43 (12 godine, 2 mjeseci)
Let
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
be a positive integer and let
![a_1](/media/m/6/1/7/6173ac27c63013385bea9def9ff2b61e.png)
,
![a_2](/media/m/4/0/1/401f4cdfec59fba73ae32fa6769c72cb.png)
,
![a_3](/media/m/e/5/1/e517d36771b6a4db32de5ee281210809.png)
, ...,
![a_k](/media/m/8/f/f/8ffe60c23d3334cc61d0660473bf1b61.png)
(
![k \geqslant 2](/media/m/a/c/2/ac29cfb6e283b999e6e17ec8e26b7345.png)
) be distinct integers in the set
![\left\{1,\,2,\,\ldots,\,n\right\}](/media/m/e/d/9/ed9c740a1b23c7e3d90350414f9d0f50.png)
such that
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
divides
![a_i \left(a_{i + 1} - 1\right)](/media/m/5/1/c/51ce1a8b99ae24d58e6475c9f2a5242f.png)
for
![i = 1,\,2,\,\ldots,\,k - 1](/media/m/9/1/e/91e4ff0bd638adab3140c658ed205817.png)
. Prove that
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
does not divide
![a_k \left(a_1 - 1\right)](/media/m/8/c/e/8ce3c5d3c917cd35cd523d16f08d3374.png)
.
Proposed by Ross Atkins, Australia
%V0
Let $n$ be a positive integer and let $a_1$, $a_2$, $a_3$, ..., $a_k$ ($k \geqslant 2$) be distinct integers in the set $\left\{1,\,2,\,\ldots,\,n\right\}$ such that $n$ divides $a_i \left(a_{i + 1} - 1\right)$ for $i = 1,\,2,\,\ldots,\,k - 1$. Prove that $n$ does not divide $a_k \left(a_1 - 1\right)$.
Proposed by Ross Atkins, Australia
Upozorenje: Ovaj zadatak još niste riješili!
Kliknite ovdje kako biste prikazali rješenje.
Drugačije zapisan uvijet zadatka glasi
![a_ia_{i+1} \equiv a_i \pmod n](/media/m/4/8/e/48e3ff63dc61c9493b1ec5659463e57a.png)
Iz
![a_1a_2 \equiv a_1 \pmod n](/media/m/f/e/6/fe66ea11a57e343465b0a86043b76329.png)
i
![a_2a_3 \equiv a_2 \pmod n](/media/m/f/7/d/f7d2252119bc5f754c1ed7a6df5d49a0.png)
slijedi
![a_1a_2a_3 \equiv a_1 \pmod n](/media/m/b/d/a/bda2e0c3d9e93314bb7a2738b64c2436.png)
Analogno dobivamo
![a_1a_2...a_k \equiv a_1 \pmod n](/media/m/c/7/0/c700b3f1a871c3f29ef1a430e338f853.png)
Pretpostavimo da vrijedi
![a_ka_1 \equiv a_k \pmod n \newline \Leftrightarrow a_ka_1a_2 \equiv a_k \pmod n \newline \Leftrightarrow a_1a_2a_3...a_k \equiv a_k \pmod n \newline \Leftrightarrow a_1 \equiv a_k \pmod n](/media/m/3/b/9/3b9549fc1b5440df6b0375cc75c0149e.png)
Pa iz uvjeta
![a_i \in \{1,2,..,n \} \forall i \Rightarrow a_1=a_k](/media/m/f/a/9/fa970b91fd269f152b7b9ab898864f2f.png)
Što je kontradikcija.
%V0
Drugačije zapisan uvijet zadatka glasi $ a_ia_{i+1} \equiv a_i \pmod n $
Iz $ a_1a_2 \equiv a_1 \pmod n $ i $ a_2a_3 \equiv a_2 \pmod n $ slijedi $ a_1a_2a_3 \equiv a_1 \pmod n $
Analogno dobivamo $ a_1a_2...a_k \equiv a_1 \pmod n $
Pretpostavimo da vrijedi
$ a_ka_1 \equiv a_k \pmod n \newline \Leftrightarrow a_ka_1a_2 \equiv a_k \pmod n \newline \Leftrightarrow a_1a_2a_3...a_k \equiv a_k \pmod n \newline \Leftrightarrow a_1 \equiv a_k \pmod n$
Pa iz uvjeta $ a_i \in \{1,2,..,n \} \forall i \Rightarrow a_1=a_k$ Što je kontradikcija.
2. svibnja 2012. 21:05 | rigoletto | Točno |
4. svibnja 2012. 12:08 | grga | Točno |