Binomial-theorem wrote:

My Solution

I guess its wrong. However here is my attempt of a proof considering gcds

Solution :

Assume that $n \mid a_i (a_{i+1} - 1)$ (indices modulo $k$ ) for all $i \ge 1$ .

Let us define the sequence $\left \langle g_i \right \rangle_{i \ge 1}$ , with indices modulo $k$ such that $g_i = \gcd(a_i,n)$ . Since $n \mid a_i(a_{i+1} - 1)$ and $\gcd (\frac{a_i}{g_i}, \frac{n}{g_i})= 1$ , we must have $\frac {n}{g_i} \mid a_{i+1} - 1$

But $\gcd(a_{i+1}, a_{i+1}- 1) = 1$ so $\gcd( g_{i+1} , \frac{n}{g_i}) = 1$ . Since $g_{i+1} \mid n$ and $\gcd( g_{i+1} , \frac{n}{g_i}) = 1$ we have $g_{i+1} \mid g_i$ . Which means $g_1 \mid g_k \mid g_{k-1} \mid \cdots \mid g_1$ . So $g_1 = g_2 = \cdots = g_k = t$ (let) . Which means $\gcd (t, \frac nt) = 1$ . So $t \mid a_i$ and $t \mid a_j$ , which gives $t \mid a_i - a_j$ . Again $\frac nt \mid a_i - 1$ and $\frac nt \mid a_j - 1$ giving $\frac nt \mid a_i - a_j$ . Since $\gcd (t, \frac nt) = 1$ , we get $n \mid a_i - a_j$ . Which is a contradiction since $a_i \ne a_j$ and $n >|a_i - a_j|$ .

About

Site Info

Help

Stay Connected