n divides 2^(n-1)+3^(n-1)

For students of class 9-10 (age 14-16)
User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:
n divides 2^(n-1)+3^(n-1)

Unread post by Phlembac Adib Hasan » Sat Feb 23, 2013 8:16 pm

Find every positive integer $n$ that divides $2^{n-1}+3^{n-1}$.

User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am

Re: n divides 2^(n-1)+3^(n-1)

Unread post by Thanic Nur Samin » Thu Jan 30, 2014 10:55 am

$2^{n-1}+3^{n-1}\equiv0(mod n)$
Multiplying $2^{n-1}-3^{n-1}$ in both sides,
$2^{2n-2}-3^{2n-2}\equiv0(mod n)$
$2^{2n-2}\equiv3^{2n-2}(mod n)$

But they are co-prime.So $n$ can only be $1$
Last edited by Thanic Nur Samin on Fri Jan 31, 2014 9:33 am, edited 1 time in total.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

User avatar
asif e elahi
Posts:185
Joined:Mon Aug 05, 2013 12:36 pm
Location:Sylhet,Bangladesh

Re: n divides 2^(n-1)+3^(n-1)

Unread post by asif e elahi » Thu Jan 30, 2014 10:27 pm

Thanic Nur Samin wrote: $2^{n-1} \equiv - 3^{n-1}(mod n)$
$=>2\equiv-3(mod n)$
Can you prove this?

User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am

Re: n divides 2^(n-1)+3^(n-1)

Unread post by Thanic Nur Samin » Fri Jan 31, 2014 9:34 am

Check the new one.Thanks for informing the mistake.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

User avatar
asif e elahi
Posts:185
Joined:Mon Aug 05, 2013 12:36 pm
Location:Sylhet,Bangladesh

Re: n divides 2^(n-1)+3^(n-1)

Unread post by asif e elahi » Fri Jan 31, 2014 11:14 am

Thanic Nur Samin wrote: $2^{2n-2}\equiv3^{2n-2}(mod n)$

But they are co-prime.So $n$ can only be $1$
Why $n$ doesn't divide $2^{2n-2}-3^{2n-2}$?.

User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am

Re: n divides 2^(n-1)+3^(n-1)

Unread post by Thanic Nur Samin » Fri Jan 31, 2014 1:09 pm

Canceling the powers we get $2\equiv3(mod n)$Substracting 2 gives us $0\equiv1(mod n)$

Am I making a mistake?
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

User avatar
Fatin Farhan
Posts:75
Joined:Sun Mar 17, 2013 5:19 pm
Location:Kushtia,Bangladesh.
Contact:

Re: n divides 2^(n-1)+3^(n-1)

Unread post by Fatin Farhan » Fri Jan 31, 2014 2:32 pm

Thanic Nur Samin wrote:Canceling the powers we get $$2\equiv3(mod n)$$
Substracting 2 gives us $$0\equiv1(mod n)$$

Am I making a mistake?
How would you cancel power?
$$5^2\equiv3^2(mod16)$$
which tells
$$5\equiv3(mod16)$$
but it's impossible.
"The box said 'Requires Windows XP or better'. So I installed L$$i$$nux...:p"

User avatar
asif e elahi
Posts:185
Joined:Mon Aug 05, 2013 12:36 pm
Location:Sylhet,Bangladesh

Re: n divides 2^(n-1)+3^(n-1)

Unread post by asif e elahi » Fri Jan 31, 2014 11:44 pm

Thanic Nur Samin wrote:Canceling the powers we get $2\equiv3(mod n)$Substracting 2 gives us $0\equiv1(mod n)$

Am I making a mistake?
You cannot cancel powers.Fatin is right.

User avatar
asif e elahi
Posts:185
Joined:Mon Aug 05, 2013 12:36 pm
Location:Sylhet,Bangladesh

Re: n divides 2^(n-1)+3^(n-1)

Unread post by asif e elahi » Sat Feb 01, 2014 12:44 am

Obviously $n=1$ is a solution.We prove that this is the only solution.We assume there exists a solution $n$. $n$ must be odd.So all the prime divisors of $n$ are odd.We take a prime $p$ such that $\nu _{2}(p-1)\leq \nu _{2}(q-1)$.Let $\nu _{2}(p-1)=d$. Then all the prime divisors of $n$ are congruent to $1$ mod $2^{d}$. So $n\equiv 1(mod 2^{d})$.
$2^{n-1}\equiv -3^{n-1}\equiv (p+3)^{n-1}$(mod p) where
or $-1\equiv (\frac{p+3}{2})^{n-1}\equiv x^{n-1}$(mod p)
Let $n=pk$. $x^{n-1}\equiv x^{pk-1}\equiv x^{k-1}\equiv -1$(mod p)
or $x^{2(k-1)}\equiv 1$(mod p)
By FLT $x^{p-1}\equiv 1$(mod p)
Let $ord_{p}(x)=c$. So $c\mid p-1$ and $c\mid 2(k-1)$.
Let $c=2^{a}b$ where b is odd.As c divides p-1,$a\leq d$.
Let $k-1=2^{r}s$ where s is odd. Note $k\equiv 1(mod 2^{d})$. So $r\geq d$.
$c\mid 2(k-1)$
or $2^{a}b\mid 2^{r+1}s$
This implies $b\mid s$
So $2^{a}b\mid 2^{a}s\mid 2^{d}s\mid 2^{r}s$
or $c$ divides $k-1$
So $x^{k-1}\equiv 1$(mod p)
But $x^{k-1}\equiv -1$(mod p)
So $p$ divides $2$ which is impossible.
So our assumption was wrong and $n=1$ is the only solution. :D

Post Reply