 mersenneforum.org Divisible by a Prime
 Register FAQ Search Today's Posts Mark Forums Read  2007-09-09, 21:52 #1 davar55   May 2004 New York City 3×17×83 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 9A316 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

22×33×19 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 7·13·17 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 2,467 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 423310 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 10000100010012 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 Show Printable Version Email this Page 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 03:00.

Mon May 10 03:00:46 UTC 2021 up 31 days, 21:41, 0 users, load averages: 2.37, 2.52, 2.15