Post Number:#65 by ahmedittihad » Mon Jun 26, 2017 3:44 am
Solution to problem $24$ (OVERKILL)
We prove by contradiction.
Assume that $n$ divides $a_k(a_1-1)$.
Assume that $(a_i, n)=1$. Then $n| a_i(a_{i+1}-1)$ implies $n|a_{i+1}-1$ which implies $a_{i+1}=1$. Then $n|1(a_{i+2}-1)$ which is only possible if $a_{i+2}=1$ but this contradicts the distinction.
So there exist some prime $p$ such that $p|n$ and $p|a_i$.
Now we inductively prove that $p$ divides all $a_j$ such that $1\leq j \leq n$. We have already shown the base case. Now assume that $p|a_m$. We have, $p |n |a_{m-1}(a_m-1)$. So, we must have $p|a_{m-1}$. Here, the indices are taken modulo $k$. So, $p$ divides all $a_j$ such that $1\leq j \leq n$. Note that the induction was done by starting from $a_i$. We get that if some prime divides at least one of the $a_j$'s, that prime divides all the $a_j$'s.
We will strengthen the statement more with dealing with prime powers.
Assume that $p^x||n$. Then,as $p^x||n|a_j(a_{j+1}-1)$ for all $j$, $p^x|a_j$ for all $j$.
So, we get that $(n,a_1)=(n,a_2)=.......=(n,a_k)= C$ where C is an integer greater than $1$.
Let, $b_j=\frac {a_j}{C}$ for all $j$. Also let, $n_1=\frac {n}{C}$. Then, we have $(n_1, C)=(n_1,b_j)=1$ for all $j$.
Now, as $n_1C|b_jC(b_{j+1}C-1)$, we get $n_1|b_{j+1}C-1$ for all $j$. So, $n_1|b_xC-1-b_yC+1=C(b_x-b_y)$.
We get that $n_1|b_x-b_y$. Which is impossible since $b_x, b_y$ are different integers less than $n_1$. So we get a contradiction. So our first assumption is false. Now, this solution is really unclear. Someone tell me where does the logic breaks if our first assumption is false.
Last edited by
ahmedittihad on Mon Jun 26, 2017 4:00 am, edited 1 time in total.
Frankly, my dear, I don't give a damn.