Home » Ask & Discuss » Mathematics. » Algebra « Back to Discussion

Algebra

Forum Expert

Joined:	18 Dec 2007
Post:	926

27 May 2008 21:39:29 IST

0 People liked this

1044

Easy challenge in Number Theory - From Feynmann

None

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 ?

Share this article on:

Comments (12)

Gaurav |spideyunlimited| Ragtah

Moderator

Joined: 16 Dec 2006

Posts: 3373

28 May 2008 00:57:08 IST

Like 4 people liked this

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.

Haresh

Cool goIITian

Joined: 15 May 2008

Posts: 81

28 May 2008 15:17:51 IST

Like 0 people liked this

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.

abhishek sinha

Forum Expert

Joined: 18 Dec 2007

Posts: 926

28 May 2008 19:27:57 IST

Like 0 people liked this

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.

Haresh

Cool goIITian

Joined: 15 May 2008

Posts: 81

28 May 2008 19:38:13 IST

Like 0 people liked this

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

abhishek sinha

Forum Expert

Joined: 18 Dec 2007

Posts: 926

29 May 2008 15:43:20 IST

Like 0 people liked this

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

Hari Shankar

Forum Expert

Joined: 28 Feb 2007

Posts: 2173

29 May 2008 16:20:41 IST

Like 0 people liked this

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?

abhishek sinha

Forum Expert

Joined: 18 Dec 2007

Posts: 926

30 May 2008 19:20:09 IST

Like 3 people liked this

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$

Hari Shankar

Forum Expert

Joined: 28 Feb 2007

Posts: 2173

31 May 2008 09:36:27 IST

Like 0 people liked this

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

abhishek sinha

Forum Expert

Joined: 18 Dec 2007

Posts: 926

31 May 2008 21:38:18 IST

Like 0 people liked this

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

Hari Shankar

Forum Expert

Joined: 28 Feb 2007

Posts: 2173

1 Jun 2008 19:07:04 IST

Like 6 people liked this

$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 kumar

Blazing goIITian

Joined: 7 Mar 2007

Posts: 784

5 Jun 2008 21:20:52 IST

Like 1 people liked this

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

Hari Shankar

Forum Expert

Joined: 28 Feb 2007

Posts: 2173

6 Jun 2008 09:17:38 IST

Like 0 people liked this

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

Quick Reply

Reply

	Some HTML allowed.
	Keep your comments above the belt or risk having them deleted.
	Signup for a avatar to have your pictures show up by your comment
	If Members see a thread that violates the Posting Rules, bring it to the attention of the Moderator Team