IIT JEE , AIEEE Forum - Mathematics , Algebra - Easy challenge in Number Theory

feynmann

Consider a sequence { ${a}_{n}$ } such that ${a}_{1}=2\;and\;{a}_{n+1}={a}_{n}^{2}-{a}_{n}+1$

How many distinct pairs chosen from this sequence have g.c.d.= 6 ?

spideyunlimited

a1 = 2. a2 = 3, a3 = 7, a4 = 43

Now since
a(n+1) = an^2 - an + 1
and after a1, the next terms are odd...
so terms will be of the type
odd^2 - odd + 1
odd^2 is always odd... and odd^2 + 1 will become even.
then even - odd = odd always....

so there won't be any distinct pair with GCD = 6... 2 will be the only even number in the sequence.

hpudipeddi

Yes Spidey unlimited is correct
All the multiples of an even number are even
Therefore all the multiples of 6 are even and according to the problem all are odd numbers except 2
therefore such ordered pairs are 0.

feynmann

Ok !

But can u tell me how many pairs of no would have g.c.d.=i ( i is a natural number ) ( as a fn of i)

Actually I am looking for a general result for any g.c.d.

hpudipeddi

once explain gcd=i.........

feynmann

that is find no of pairs as a function of i for which their g.c.d=i

hsbhatt

Hint: can you prove that every term in the sequence is prime to every other term of the sequence, i.e. all terms are mutually co-prime?

feynmann

Yes , that is the way I was talking about .

See, we have

${a}_{n+1}-1={a}_{n}({a}_{n}-1)$ ................................... (1)

= ${a}_{n}{a}_{n-1}{a}_{n-2}....{a}_{1}({a}_{1}-1)$ ( repeatedly using the formula (1) )

= ${a}_{n}{a}_{n-1}{a}_{n-2}..............{a}_{1} \;\;as\;{a}_{1}=2$

which means that ${a}_{n+1}\; is \;mutually \;coprime \;w.r.t.\;all\;{a}_{i}s \;where$ $i\le n$

which means the g.c.d. of any two numbers ${a}_{i};and\;{a}_{j}\;\forall\;i,j\in\;N\;i\ne\;j\;is \;1$

hsbhatt

Even without algebraic manipulation, you can see that $a_i \equiv 1$ (mod ) when $i \ne j$

feynmann

HOW ??? ( that is to be shown in fact !!!! )

hsbhatt

$a_{n+1} = a_n^2-a_n+1$

Hence $a_{n+1} \equiv 1 \bmod(a_n)$

i.e $a_{n+1} = ka_n+1$

Now, $a_{n+2} = a_{n+1}^2-a_{n+1}+1$ =

and hence $a_{n+2} \equiv 1 \bmod (a_n)$

In this way, we can prove that $a_k \equiv 1 \bmod(a_n)$ when k>n

By the same argument , we can prove that $a_k \equiv 1 \bmod(a_n)$ when k<n too.

Thus, the result that $a_i \equiv 1 \bmod {a_j}$ when $i \ne j$

kislay

hsbhatt sir

u said

".By the same argument , we can prove that $a_k \equiv 1 \bmod(a_n)$ when k<n too."

could u plz show it ...i do not think it is possible

hsbhatt

yeah actually you are right as it contradicts the result for k>n.

So, the result has to be reworded as $a_i \equiv 1 \bmod (a_j)\ \text{when} \ i>j$

and thus $gcd(a_i, a_j) = 1, i\ne j$

Thanks for pointing out the error

Ask & Discuss Questions with Community & Experts