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

Algebra

Blazing goIITian

Joined:	12 Apr 2008
Post:	2717

13 Jun 2009 21:30:33 IST

0 People liked this

464

Prove:

None

This is a question that I came accross in one of the forums which i would like to share:

Prove that if is greater than and divisible by , but not divisible by , then, $\frac n{2}+1$ is the remainder when $\left(\frac n{2}+1\right)^k$ is divided by where is a natural number.

Share this article on:

Comments (5)

RyuAmakusa

Blazing goIITian

Joined: 21 Mar 2008

Posts: 776

13 Jun 2009 22:09:25 IST

Like 2 people liked this

$\text{The no. should be of the form 4a+2 so we hav to find the remainder of }\\\\\frac{{(2a+2)}^k}{4a+2}\\\\ \text{2 times the remainder of } \frac{(a+1){((2a+1)+1)}^{k-1}}{2a+1}\\\\ \text{That is 2a+2 = }\frac{n}{2}+1$

sutanoy dasgupta

Hot goIITian

Joined: 12 Sep 2008

Posts: 127

13 Jun 2009 22:38:38 IST

Like 1 people liked this

n/2 + 1 = x ,say.(x is even due to the conditions on n)

to prove that x^k-x is divisible by 2(x-1):

x^k-x=x(x^k-1-1) k-1>=0;

expanding (x^k-1-1) ,we get (x-1)(1+x+....)

thus {x(x-1)(1+x+...)}/{2(x-1)} is an integer.

hence proved.

Hari Shankar

Forum Expert

Joined: 28 Feb 2007

Posts: 2173

14 Jun 2009 12:13:52 IST

Like 3 people liked this

We only need to prove that $left( rac{n}{2} + 1ight)^2 equiv rac{n}{2}+1 mod{n}$

Now $left( rac{n}{2} + 1ight)^2 - rac{n}{2}+1 = rac{n(n+2)}{4}$ . Now, n+2 is divisible by 4 i.e. n+2/4 is an integer.

This means $left( rac{n}{2} + 1ight)^2 -left( rac{n}{2}+1ight) equiv 0 mod n$ or $left( rac{n}{2} + 1ight)^2 equivleft( rac{n}{2}+1ight) mod n$ as required

From this it follows that $left( rac{n}{2} + 1 ight)^k equivleft( rac{n}{2}+1 ight)^{k-1} mod n$

So that $left( rac{n}{2} + 1 ight)^k equivleft( rac{n}{2}+1 ight)^{k-1} equiv left( rac{n}{2}+1 ight)^{k-2} equiv ...equiv left( rac{n}{2}+1 ight) mod n$

asdfg

New kid on the Block

Joined: 28 May 2009

Posts: 18

15 Jun 2009 12:21:36 IST

Like 0 people liked this

@hari sir

the second step should be

Hari Shankar

Forum Expert

Joined: 28 Feb 2007

Posts: 2173

15 Jun 2009 12:26:09 IST

Like 0 people liked this

yeah, thats a typo. the rest of working is correct

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