n^2|2^n+1

Discussion on International Mathematical Olympiad (IMO)
User avatar
Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm
Location: Dhaka,Bangladesh

n^2|2^n+1

Unread post by Masum » Thu Mar 24, 2011 3:57 pm

Some months ago I created a problem:
Find all $n\in\mathbb N$ such that $n|2^n+1$
Later I found that an IMO problem required to find all $n\in\mathbb N$ such that $n^2|2^n+1$
Now do both!
One one thing is neutral in the universe, that is $0$.

User avatar
Tahmid Hasan
Posts: 665
Joined: Thu Dec 09, 2010 5:34 pm
Location: Khulna,Bangladesh.

Re: n^2|2^n+1

Unread post by Tahmid Hasan » Sun Apr 03, 2011 11:39 am

first 1 holds iff n is a prime other than 2 (fermat's pichhi thm).
বড় ভালবাসি তোমায়,মা

User avatar
Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm
Location: Dhaka,Bangladesh

Re: n^2|2^n+1

Unread post by Masum » Mon Apr 04, 2011 7:26 pm

Tahmid Hasan wrote:first 1 holds iff n is a prime other than 2 (fermat's pichhi thm).
I didn't understand what you meant?$n=p>2$? Or else.
One one thing is neutral in the universe, that is $0$.

User avatar
Tahmid Hasan
Posts: 665
Joined: Thu Dec 09, 2010 5:34 pm
Location: Khulna,Bangladesh.

Re: n^2|2^n+1

Unread post by Tahmid Hasan » Mon Apr 04, 2011 10:39 pm

i said n has to be an odd prime
বড় ভালবাসি তোমায়,মা

User avatar
Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm
Location: Dhaka,Bangladesh

Re: n^2|2^n+1

Unread post by Masum » Tue Apr 05, 2011 5:18 pm

You meant $31|2^{31}+1=2147483649$ for example?
If so,you are wrong,and the original answer is not like that at all,you are true only for $n=3$.Else you are wrong.
why don't you check some easy counter examples?
For example $5\not|2^5+1=33$
According to your assumption,$2^p\equiv -1\pmod p,2^{2p}\equiv 1\pmod p$ and by Fermat's Little Theorem,$2^{p-1}\equiv1\pmod p$
These two imply $2^{gcd(2p,p-1)}\equiv 1\Longrightarrow 2^2\equiv 1\Longrightarrow p=3$
So this is of-course wrong.
Great Hint:
Look at the smallest prime factor of $n$,say it is $p$.Then let $n=p^{v_p(n)}q$ with $p\not|q$.Again if $q>1$,what follows from the same approach?
One one thing is neutral in the universe, that is $0$.

Post Reply