S.O.S. Mathematics CyberBoard

Your Resource for mathematics help on the web!
It is currently Sun, 26 May 2013 02:04:47 UTC

View unanswered posts | View active topics


Board index » Advanced Mathematics » Algebra and Number Theory

All times are UTC [ DST ]



Post new topic Reply to topic  Page 1 of 1
  [ 8 posts ] 
  Print view Previous topic | Next topic 
Author Message
m2012
 Post subject: sum of squares
PostPosted: Sat, 2 Jun 2012 15:40:04 UTC 
Offline
Math Cadet

Joined: Sat, 2 Jun 2012 15:31:17 UTC
Posts: 8
Find all positive integers n such that the number 2^n-1 has a multiple of the form m^2+9.
Top
 Profile  
 
outermeasure
 Post subject: Re: sum of squares
PostPosted: Sat, 2 Jun 2012 15:51:22 UTC 
Offline
Moderator
User avatar

Joined: Mon, 29 Dec 2008 17:49:32 UTC
Posts: 6009
Location: 127.0.0.1, ::1 (avatar courtesy of UDN)
m2012 wrote:
Find all positive integers n such that the number 2^n-1 has a multiple of the form m^2+9.


Where does this problem come from? What have you tried?

_________________
\begin{aligned} Spin(1)&=O(1)=\mathbb{Z}/2&\quad&\text{and}\\ Spin(2)&=U(1)=SO(2)&&\text{are obvious}\\ Spin(3)&=Sp(1)=SU(2)&&\text{by }q\mapsto(\mathop{\mathrm{Im}}\mathbb{H}\ni p\mapsto qp\bar{q})\\ Spin(4)&=Sp(1)\times Sp(1)&&\text{by }(q_1,q_2)\mapsto(\mathbb{H}\ni p\mapsto q_1p\bar{q_2})\\ Spin(5)&=Sp(2)&&\text{by }\mathbb{HP}^1\cong S^4_{round}\hookrightarrow\mathbb{R}^5\\ Spin(6)&=SU(4)&&\text{by the irrep }\Lambda_+\mathbb{C}^4 \end{aligned}
Top
 Profile  
 
m2012
 Post subject: Re: sum of squares
PostPosted: Sat, 2 Jun 2012 15:57:18 UTC 
Offline
Math Cadet

Joined: Sat, 2 Jun 2012 15:31:17 UTC
Posts: 8
It's from IMO 1999 Shortlist. I think i can show that n must be a power of two.
Top
 Profile  
 
rdj5933mile5math64
 Post subject: Re: sum of squares
PostPosted: Mon, 4 Jun 2012 17:38:41 UTC 
Offline
Senior Member
User avatar

Joined: Wed, 4 Apr 2012 03:51:40 UTC
Posts: 129
Location: Hockeytown aka Detroit
m2012 wrote:
It's from IMO 1999 Shortlist.


It is actually a shortlist problem from 1998.

m2012 wrote:
I think i can show that n must be a power of two.


Tip 1:

Spoiler:
Define you're givens: in this problem let all n satisfying the condition be defined as a good number and let all other numbers be called bad numbers. If m is a natural number such that 2^n-1 \mid m^2+9, then we say that m is an n-awesome number, otherwise we call m an n-uncool number. These help in the "Tip 2" section.


Tip 2:

Spoiler:
Try lots of different numbers: in this problem you should compute a lot of m^2+9 numbers and 2^n-1 numbers. This gave me the hunch that the answer was n=2^k.


Motivation:

Spoiler:
The problem is equivalent to showing that -9 is a quadratic residue mod 2^n-1.


So, in this problem we have to do 2 things. We have to find all of the numbers that work and show that no other numbers work.

Claim:

Spoiler:
I claim that a number is a good number iff the number is a power of 2.


Showing bad numbers don't work:

Spoiler:
First, we show that a number that is not a power of 2 is a bad number. We know that if k \mid x, then 2^k-1 \mid 2^x-1 so all we would have to work on is when n is odd. But, since 2^n-1 \equiv 3 \pmod{4} it has a prime factor of 4t+3 which isn't 3. But, this is impossible.



Showing good numbers work:

Spoiler:
I thought "Induction probably a good idea because we have n=2^k." Turned out inducting worked. Base Cases are triv. Use 2^{2^k}-1=(2^{2^{k-1}}+1)(2^{2^{k-1}}-1). Then by inductive hypothesis and (3 \cdot 2^{2^{n-2}})^2=9\cdot 2^{2^{m-1}} we can use CRT and we are done.


EDIT: I decided to elaborate on the section "Showing good numbers work".

_________________
math puns are the first sine of madness
-JDR
:mrgreen:
Top
 Profile  
 
outermeasure
 Post subject: Re: sum of squares
PostPosted: Tue, 5 Jun 2012 09:40:26 UTC 
Offline
Moderator
User avatar

Joined: Mon, 29 Dec 2008 17:49:32 UTC
Posts: 6009
Location: 127.0.0.1, ::1 (avatar courtesy of UDN)
rdj5933mile5math64 wrote:
But, since 2^n-1 \equiv 3 \pmod{4} it has a prime factor of 4t+3 which isn't 3


Local counterexample: 27\equiv 3\pmod{4} (indeed, any odd power of 3 multiplied by a bunch of 1(mod 4)-primes in place of 27 would do, as does n a power of 2) but it doesn't have a 3(mod 4) prime factor which isn't 3. You need to use 2^n\equiv 2\pmod{3} too.

_________________
\begin{aligned} Spin(1)&=O(1)=\mathbb{Z}/2&\quad&\text{and}\\ Spin(2)&=U(1)=SO(2)&&\text{are obvious}\\ Spin(3)&=Sp(1)=SU(2)&&\text{by }q\mapsto(\mathop{\mathrm{Im}}\mathbb{H}\ni p\mapsto qp\bar{q})\\ Spin(4)&=Sp(1)\times Sp(1)&&\text{by }(q_1,q_2)\mapsto(\mathbb{H}\ni p\mapsto q_1p\bar{q_2})\\ Spin(5)&=Sp(2)&&\text{by }\mathbb{HP}^1\cong S^4_{round}\hookrightarrow\mathbb{R}^5\\ Spin(6)&=SU(4)&&\text{by the irrep }\Lambda_+\mathbb{C}^4 \end{aligned}
Top
 Profile  
 
rdj5933mile5math64
 Post subject: Re: sum of squares
PostPosted: Tue, 5 Jun 2012 17:45:33 UTC 
Offline
Senior Member
User avatar

Joined: Wed, 4 Apr 2012 03:51:40 UTC
Posts: 129
Location: Hockeytown aka Detroit
outermeasure wrote:
rdj5933mile5math64 wrote:
But, since 2^n-1 \equiv 3 \pmod{4} it has a prime factor of 4t+3 which isn't 3


Local counterexample: 27\equiv 3\pmod{4} (indeed, any odd power of 3 multiplied by a bunch of 1(mod 4)-primes in place of 27 would do, as does n a power of 2) but it doesn't have a 3(mod 4) prime factor which isn't 3. You need to use 2^n\equiv 2\pmod{3} too.


Oops. Unfortunately, the statement 2^n \equiv 2 \pmod{3} for n odd didn't make it from my notebook to my post.

_________________
math puns are the first sine of madness
-JDR
:mrgreen:
Top
 Profile  
 
m2012
 Post subject: Re: sum of squares
PostPosted: Wed, 6 Jun 2012 21:11:41 UTC 
Offline
Math Cadet

Joined: Sat, 2 Jun 2012 15:31:17 UTC
Posts: 8
Thanks for the answers. How can we use CRT in induictive proof that the powers of 2 are "good numbers"?
Top
 Profile  
 
outermeasure
 Post subject: Re: sum of squares
PostPosted: Thu, 7 Jun 2012 09:34:59 UTC 
Offline
Moderator
User avatar

Joined: Mon, 29 Dec 2008 17:49:32 UTC
Posts: 6009
Location: 127.0.0.1, ::1 (avatar courtesy of UDN)
m2012 wrote:
Thanks for the answers. How can we use CRT in induictive proof that the powers of 2 are "good numbers"?


Recall 2^{2^n}-1=F_0F_1\dots F_{n-1} where F_k=2^{2^k}+1 is the kth Fermat number. Also recall the Fermat numbers are pairwise coprime. Use CRT on the system m\equiv 0\pmod{3},\quad m\equiv\pm 3\cdot 2^{2^{k-1}}\pmod{F_k}},\quad 1\leq k\leq n-1, or inductively:
m_1\equiv 0\pmod{3}, and
\left\{ \begin{aligned} m_{k+1}&\equiv m_k\pmod{(2^{2^k}-1)}\\ m_{k+1}&\equiv\pm 3\cdot 2^{2^k}\pmod{F_{k+1}} \end{aligned}\right.

_________________
\begin{aligned} Spin(1)&=O(1)=\mathbb{Z}/2&\quad&\text{and}\\ Spin(2)&=U(1)=SO(2)&&\text{are obvious}\\ Spin(3)&=Sp(1)=SU(2)&&\text{by }q\mapsto(\mathop{\mathrm{Im}}\mathbb{H}\ni p\mapsto qp\bar{q})\\ Spin(4)&=Sp(1)\times Sp(1)&&\text{by }(q_1,q_2)\mapsto(\mathbb{H}\ni p\mapsto q_1p\bar{q_2})\\ Spin(5)&=Sp(2)&&\text{by }\mathbb{HP}^1\cong S^4_{round}\hookrightarrow\mathbb{R}^5\\ Spin(6)&=SU(4)&&\text{by the irrep }\Lambda_+\mathbb{C}^4 \end{aligned}
Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  Page 1 of 1
  [ 8 posts ] 

Board index » Advanced Mathematics » Algebra and Number Theory

All times are UTC [ DST ]

Who is online

Users browsing this forum: No registered users

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

Search for:
Jump to:  
Contact Us | S.O.S. Mathematics Homepage
Privacy Statement | Search the "old" CyberBoard

users online during the last hour
Powered by phpBB © 2001, 2005-2011 phpBB Group.
Copyright © 1999-2013 MathMedics, LLC. All rights reserved.
Math Medics, LLC. - P.O. Box 12395 - El Paso TX 79913 - USA