mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2007-09-09, 21:52   #1
davar55
 
davar55's Avatar
 
May 2004
New York City

423310 Posts
Default Divisible by a Prime

Let p be a prime of form 4n+1 for some positive integer n.

Show there exists a positive integral x such that p divides x^2 + 1.

In other words, for any such p, show that the diophantine equation
x^2 + 1 = p*y has a solution in positive integers x,y.

(In fact there is such a solution with x < p).
davar55 is offline   Reply With Quote
Old 2007-09-09, 22:26   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

We want x^2 == -1 (mod p), and -1 is a QR mod p with p odd iff p == 1 (mod 4)... There's not much to say about this puzzle, the solution follows directly from elementary number theory.

Alex
akruppa is offline   Reply With Quote
Old 2007-09-10, 00:20   #3
Kevin
 
Kevin's Avatar
 
Aug 2002
Ann Arbor, MI

433 Posts
Default

All you did was restate the problem. The puzzle is to prove that theorem (or at least one direction of it).
Kevin is offline   Reply With Quote
Old 2007-09-10, 01:49   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by Kevin View Post
All you did was restate the problem. The puzzle is to prove that theorem (or at least one direction of it).
I don't read it that way. Quadratic Reciprocity is a fundamental result.
Using it hardly calls for proving it at the same time.
R.D. Silverman is offline   Reply With Quote
Old 2007-09-10, 17:35   #5
davar55
 
davar55's Avatar
 
May 2004
New York City

3·17·83 Posts
Default

The "puzzle" as presented in my source was intended to
be solved from "elementary" number theory, without using
results derived from something powerful like the Quadratic
Reciprocity Theorem. However, point taken -- given QR,
there is practically no puzzle.

Anyway, the puzzle book solution uses Wilson's theorem
(arguably simpler than QR)
to derive a specific, explicit formula for the value of x
sought for in the original problem statement.
Finding such a formula is still open as a simple challenge.
(Kind of constructivist I admit.)

Last fiddled with by davar55 on 2007-09-10 at 17:35
davar55 is offline   Reply With Quote
Old 2007-09-11, 07:51   #6
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

1000000001002 Posts
Thumbs up

Quote:
Originally Posted by davar55 View Post
The "puzzle" as presented in my source was intended to...
However, point taken -- given QR,
there is practically no puzzle.

Anyway, the puzzle book solution uses Wilson's theorem
(arguably simpler than QR)
to derive a specific, explicit formula for the value of x
sought for in the original problem statement.
Finding such a formula is still open as a simple challenge.
(Kind of constructivist I admit.)


Well Davar, being an ardent researcher in elementary theory, I am interested in any method used to get to the solution.

If as you say, it is simpler than QR then it is worth considering.

My 'Beth theorem' is also simple but unknown to the math world and awaits peer review and publication.

I firmly believe that it is easier to find an attractive sea shell or round pebble on the beach, or in shallow waters, than by fishing in the deep.



I mean in mathematics, but it also applies to other pastimes too, as my ample travels prove. I loved rambling on the beaches of Mauritius to name one such.

Mally
mfgoode is offline   Reply With Quote
Old 2007-09-11, 13:38   #7
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

110000010112 Posts
Default

Let p be a prime congruent to 1 mod 4. There is an element y with the order of y (modulo p) equal to p-1. Set x=y^((p-1)/4) mod p. This is the x you want.
Zeta-Flux is offline   Reply With Quote
Old 2007-09-11, 14:15   #8
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46438 Posts
Default

I thought about posting that, too, but it uses group theory... maybe that is not elementary enough, either. I guess typing a proof of Quadratic Reciprocity off a text book would count as a solution, but how boring is that...

Alex
akruppa is offline   Reply With Quote
Old 2007-09-11, 16:35   #9
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

7·13·17 Posts
Default

True. Although it is only a tiny bit of group theory. But then, starting from scratch, it takes a while to even *define* primes and what division is, and so forth. So one has to start somewhere.

If one isn't familiar with the fact that (Z/pZ)* is a cyclic group of order p-1, the proof isn't difficult.

1. Prove it is a group. (Easy)
2. Prove that Z/pZ is a field. (Easy)
3. Prove that if (Z/pZ)* has an element g_1 of order a, and an element g_2 of order b, then it has an element g_3 of order lcm(a,b). (Fairly easy)
4. Use #3 to prove that there is a (minimal) positive integer d, with x^d=1 for all x\in (Z/pZ)* AND there is an element in (Z/pZ)* of order d. (Straightforward. Just take the lcm of all the orders of each of the finitely many elements.)
5. Notice that x^d-1 can only have d roots (since Z/pZ is a field). But (Z/pZ)* has p-1 elements satisfying x^d-1=0. Thus d>=p-1.
6. Use Fermat's little theorem to get d<=p-1. [Proving Fermat's little theorem is easy. One uses induction, the binomial theorem, and the fact that p|(p choose a) for integers in the interval 0<a<p.]
7. Conclude d=p-1.
Zeta-Flux is offline   Reply With Quote
Old 2007-09-11, 20:43   #10
davar55
 
davar55's Avatar
 
May 2004
New York City

3·17·83 Posts
Default

How do you compute the element y of order d=p-1 ?
Does this amount to solving y^(p-1) = 1 over Z/pZ ?
Is there a simple formula derivable for y and thus x=y^((p-1)/4) (mod p)?

Quadratic reciprocity and group theoretic results are
more than fine, they are the substance of real math.
So I'll humbly present the solution I have.

Given prime p=4n+1 divides (p-1)! + 1 (from Wilson's Theorem).
But (p-1)! = 1*2*3*...*4n
= 1*2*3*...*2n*(p-2n)*(p-(2n-1))*(p-(2n-2))*...*(p-1)
Multiplying the terms containing p gives Ap + (2n)! for some A.
So (p-1)! + 1 = (2n)! * (Ap + (2n)!) + 1 = Bp + (2n!)^2 + 1 for some B.
Since the LHS is divisible by p, so also must be (2n)!^2 + 1.
So x = (2n)! satisfies the original problem.
Of course, letting x = a*p + x' shows x'^2 + 1 is also divisible by p,
so reducing to x = (2n)! (mod p) satisifies x < p as well.
davar55 is offline   Reply With Quote
Old 2007-09-11, 21:49   #11
davar55
 
davar55's Avatar
 
May 2004
New York City

102118 Posts
Default

I left out the obvious last step, that x = ((p-1)/2)! (mod p)
is thus a solution to the original problem.
davar55 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Prime Gap Length with consecutive integers divisible by small primes carpetpool Prime Gap Searches 45 2017-09-30 20:51
2LMs with exponent divisible by 13 Batalov Cunningham Tables 1 2011-04-14 10:23
5th RPS Drive: 14 Ks < 300 divisible by 3 Kosmaj Riesel Prime Search 756 2008-07-04 12:50
Divisible by 7 ? davar55 Puzzles 4 2007-08-09 20:10
Divisible by 7 davar55 Puzzles 3 2007-05-14 22:05

All times are UTC. The time now is 13:20.

Sat May 15 13:20:46 UTC 2021 up 37 days, 8:01, 0 users, load averages: 1.87, 1.99, 1.84

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.