mersenneforum.org Divisible by a Prime
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2007-09-09, 21:52 #1 davar55     May 2004 New York City 423310 Posts 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).
 2007-09-09, 22:26 #2 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts 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
 2007-09-10, 00:20 #3 Kevin     Aug 2002 Ann Arbor, MI 433 Posts All you did was restate the problem. The puzzle is to prove that theorem (or at least one direction of it).
2007-09-10, 01:49   #4
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by Kevin 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.

 2007-09-10, 17:35 #5 davar55     May 2004 New York City 3·17·83 Posts 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
2007-09-11, 07:51   #6
mfgoode
Bronze Medalist

Jan 2004
Mumbai,India

1000000001002 Posts

Quote:
 Originally Posted by davar55 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

 2007-09-11, 13:38 #7 Zeta-Flux     May 2003 110000010112 Posts 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.
 2007-09-11, 14:15 #8 akruppa     "Nancy" Aug 2002 Alexandria 46438 Posts 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
 2007-09-11, 16:35 #9 Zeta-Flux     May 2003 7·13·17 Posts 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
 2007-09-11, 20:43 #10 davar55     May 2004 New York City 3·17·83 Posts 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.
 2007-09-11, 21:49 #11 davar55     May 2004 New York City 102118 Posts I left out the obvious last step, that x = ((p-1)/2)! (mod p) is thus a solution to the original problem.

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Prime Gap Searches 45 2017-09-30 20:51 Batalov Cunningham Tables 1 2011-04-14 10:23 Kosmaj Riesel Prime Search 756 2008-07-04 12:50 davar55 Puzzles 4 2007-08-09 20:10 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.