# S.O.S. Mathematics CyberBoard

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

 All times are UTC [ DST ]

 Page 1 of 1 [ 8 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: sum of squaresPosted: Sat, 2 Jun 2012 15:40:04 UTC

Joined: Sat, 2 Jun 2012 15:31:17 UTC
Posts: 8
Find all positive integers such that the number has a multiple of the form .

Top

 Post subject: Re: sum of squaresPosted: Sat, 2 Jun 2012 15:51:22 UTC
 Moderator

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 such that the number has a multiple of the form .

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

_________________

Top

 Post subject: Re: sum of squaresPosted: Sat, 2 Jun 2012 15:57:18 UTC

Joined: Sat, 2 Jun 2012 15:31:17 UTC
Posts: 8
It's from IMO 1999 Shortlist. I think i can show that must be a power of two.

Top

 Post subject: Re: sum of squaresPosted: Mon, 4 Jun 2012 17:38:41 UTC
 Senior Member

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 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 is a natural number such that , then we say that 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 numbers and numbers. This gave me the hunch that the answer was .

Motivation:

Spoiler:
The problem is equivalent to showing that is a quadratic residue mod .

So, in this problem we have to do 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 .

Spoiler:
First, we show that a number that is not a power of is a bad number. We know that if , then so all we would have to work on is when is odd. But, since it has a prime factor of which isn't 3. But, this is impossible.

Showing good numbers work:

Spoiler:
I thought "Induction probably a good idea because we have ." Turned out inducting worked. Base Cases are triv. Use . Then by inductive hypothesis and 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

Top

 Post subject: Re: sum of squaresPosted: Tue, 5 Jun 2012 09:40:26 UTC
 Moderator

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 it has a prime factor of which isn't 3

Local counterexample: (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 too.

_________________

Top

 Post subject: Re: sum of squaresPosted: Tue, 5 Jun 2012 17:45:33 UTC
 Senior Member

Joined: Wed, 4 Apr 2012 03:51:40 UTC
Posts: 129
Location: Hockeytown aka Detroit
outermeasure wrote:
rdj5933mile5math64 wrote:
But, since it has a prime factor of which isn't 3

Local counterexample: (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 too.

Oops. Unfortunately, the statement for odd didn't make it from my notebook to my post.

_________________
math puns are the first sine of madness
-JDR

Top

 Post subject: Re: sum of squaresPosted: Wed, 6 Jun 2012 21:11:41 UTC

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

 Post subject: Re: sum of squaresPosted: Thu, 7 Jun 2012 09:34:59 UTC
 Moderator

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 where is the kth Fermat number. Also recall the Fermat numbers are pairwise coprime. Use CRT on the system , or inductively:
, and

_________________

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 8 posts ]

 All times are UTC [ DST ]

#### Who is online

Users browsing this forum: No registered users

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forum

Search for:
 Jump to:  Select a forum ------------------ High School and College Mathematics    Algebra    Geometry and Trigonometry    Calculus    Matrix Algebra    Differential Equations    Probability and Statistics    Proposed Problems Applications    Physics, Chemistry, Engineering, etc.    Computer Science    Math for Business and Economics Advanced Mathematics    Foundations    Algebra and Number Theory    Analysis and Topology    Applied Mathematics    Other Topics in Advanced Mathematics Other Topics    Administrator Announcements    Comments and Suggestions for S.O.S. Math    Posting Math Formulas with LaTeX    Miscellaneous