MathLinks Forum LaTeX Help AoPS Classes Books Classroom MathLinks Contest Math Resources

The time now is Sat Nov 21, 2009 1:29 am
All times are UTC + 2		 View posts since last visit
View unanswered posts
A 71
View previous topicView next topic
Home » Forum » Olympiad Section » Number Theory » PEN » Official PEN problems » Divisibility Theory
 
 
7 Posts • Page 1 of 1
Author Message
Peter
Birch & Swinnerton Dyer
Birch & Swinnerton Dyer


Offline
Joined: 05 May 2004
Posts: 5202
Location: Ghent
Belgium
To rate posts you must be logged in
#1
A 71
IMO 1990/3 (ROM5)
Determine all integers n > 1 such that \frac{2^{n}+1}{n^{2}} is an integer.

PostPosted: Fri May 25, 2007 2:24 am
Rust
Birch & Swinnerton Dyer
Birch & Swinnerton Dyer

Offline
Joined: 10 Feb 2006
Posts: 3639
To rate posts you must be logged in
#2
Obviosly n is odd. Let p is maximal prime divisor n, suth that n^2|2^n+1 and n=mp, then p|2^m+1.
If n=p^km, v_p(m)=0, k\ge 1, then must be v_p(2^m+1)\ge k.
Therefore from all solution n we get p|2^1+1 and find minimal solution (n>1) n=3, Because 2^3+1 had not another prime factors. And all solutions are n=1 and n=3.

PostPosted: Mon Oct 15, 2007 8:51 pm
Peter
Birch & Swinnerton Dyer
Birch & Swinnerton Dyer


Offline
Joined: 05 May 2004
Posts: 5202
Location: Ghent
Belgium
To rate posts you must be logged in
#3
Rust wrote:
Let p is maximal prime divisor n, suth that n^2|2^n + 1 and n = mp, then p|2^m + 1.
Who says there is such a prime divisor?

Rust wrote:
If n = p^km, v_p(m) = 0, k\ge 1, then must be v_p(2^m + 1)\ge k.
Why?
_________________
Boo!

PostPosted: Fri Nov 02, 2007 3:16 am
chien than
Yang-Mills Theory
Yang-Mills Theory

Offline
Joined: 22 Nov 2006
Posts: 975
Location: Hanoi National University of Education,High school for gitfed student
To rate posts you must be logged in
#4
http://www.kalva.demon.co.uk/imo/isoln/isoln903.html

PostPosted: Fri Nov 02, 2007 3:46 am
kimnimalar
P versus NP
P versus NP

Offline
Joined: 24 Apr 2007
Posts: 36
To rate posts you must be logged in
#5
Rust wrote:
Obviosly n is odd. Let p is maximal prime divisor n, suth that n^2|2^n + 1 and n = mp, then p|2^m + 1.
If n = p^km, v_p(m) = 0, k\ge 1, then must be v_p(2^m + 1)\ge k.
Therefore from all solution n we get p|2^1 + 1 and find minimal solution (n>1) n = 3, Because 2^3 + 1 had not another prime factors. And all solutions are n = 1 and n = 3.


please write full, I can't understand vp(m) and others... what's mean this function?

PostPosted: Tue Jun 24, 2008 3:36 pm
ZetaX
Birch & Swinnerton Dyer
Birch & Swinnerton Dyer


Offline
Joined: 21 Dec 2004
Posts: 6123
Location: München
Germany
To rate posts you must be logged in
#6
For notations, always take a look at http://www.mathlinks.ro/viewtopic.php?t=76610 .
_________________
The one and only place to get next year's IMO problems already now!

PostPosted: Tue Jun 24, 2008 4:51 pm
Rust
Birch & Swinnerton Dyer
Birch & Swinnerton Dyer

Offline
Joined: 10 Feb 2006
Posts: 3639
To rate posts you must be logged in
#7
kimnimalar wrote:
Rust wrote:
Obviosly n is odd. Let p is maximal prime divisor n, suth that n^2|2^n + 1 and n = mp, then p|2^m + 1.
If n = p^km, v_p(m) = 0, k\ge 1, then must be v_p(2^m + 1)\ge k.
Therefore from all solution n we get p|2^1 + 1 and find minimal solution (n>1) n = 3, Because 2^3 + 1 had not another prime factors. And all solutions are n = 1 and n = 3.


please write full, I can't understand vp(m) and others... what's mean this function?

Full solution:
Because for n>1 2^n+1 is odd, n is odd. Let p is maximal prime divisor of n and n=mp^k,p\not |m. Then 2^{mp^k}=-1\mod p^{2k}m^2 and (\phi(m^2),p)=1. If m=1 obviosly m^2|2^m+1. Let m>1.Therefore exist odd u (\phi(m^2) - even if m>1 and odd), suth that p^ku=1\mod \phi(m^2).
It give 2^{mp^ku}=(-1)^u=-1 \mod m^2. Because p^ku=1\mod \phi(m^2), we get m^2|2^m+1. It give new solution m.
If p\not |2^k+1, then 2^{kp}+1=(2^{p-1})^k*2^k+1=2^k+1\mod p, therefore p\not |2^{kp}+1,...p\not |2^{kp^l}.
Because p|2^{mp^k}+1, we get p|2^m+1. Exactly p^k|2^m+1.
From solution n_0=n=p^km we get solution n_1=m^2|2^m+1, suth that p|2^m+1 and n_1 had less prime divisors, then n_0.
From n_1 we get n_2,...n_l=p^k and n_{l+1}=1. Therefore p^k|2^1+1=3\to p=3,k=1.
It give solution n=3. If n=p^k*3, then p^k|2^3+1=9. Therefore we had not another solutions.

PostPosted: Tue Jun 24, 2008 5:09 pm
Display posts from previous:   Sort by:   
7 Posts • Page 1 of 1
Home » Forum » Olympiad Section » Number Theory » PEN » Official PEN problems » Divisibility Theory
 
View previous topicView next topic
Jump to:  


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum
You cannot post calendar events in this forum

Created and Maintained by Valentin Vornicu - (c) AoPS Inc. 2004-2008