20070909, 21:52  #1 
May 2004
New York City
2^{3}×23^{2} 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). 
20070909, 22:26  #2 
"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 
20070910, 00:20  #3 
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).

20070910, 01:49  #4 
Nov 2003
2^{2}·5·373 Posts 

20070910, 17:35  #5 
May 2004
New York City
2^{3}·23^{2} 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 20070910 at 17:35 
20070911, 07:51  #6  
Bronze Medalist
Jan 2004
Mumbai,India
100000000100_{2} Posts 
Quote:
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 

20070911, 13:38  #7 
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 p1. Set x=y^((p1)/4) mod p. This is the x you want.

20070911, 14:15  #8 
"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 
20070911, 16:35  #9 
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 p1, 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^d1 can only have d roots (since Z/pZ is a field). But (Z/pZ)* has p1 elements satisfying x^d1=0. Thus d>=p1. 6. Use Fermat's little theorem to get d<=p1. [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=p1. 
20070911, 20:43  #10 
May 2004
New York City
1000010001000_{2} Posts 
How do you compute the element y of order d=p1 ?
Does this amount to solving y^(p1) = 1 over Z/pZ ? Is there a simple formula derivable for y and thus x=y^((p1)/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 (p1)! + 1 (from Wilson's Theorem). But (p1)! = 1*2*3*...*4n = 1*2*3*...*2n*(p2n)*(p(2n1))*(p(2n2))*...*(p1) Multiplying the terms containing p gives Ap + (2n)! for some A. So (p1)! + 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. 
20070911, 21:49  #11 
May 2004
New York City
1000010001000_{2} Posts 
I left out the obvious last step, that x = ((p1)/2)! (mod p)
is thus a solution to the original problem. 
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  20170930 20:51 
2LMs with exponent divisible by 13  Batalov  Cunningham Tables  1  20110414 10:23 
5th RPS Drive: 14 Ks < 300 divisible by 3  Kosmaj  Riesel Prime Search  756  20080704 12:50 
Divisible by 7 ?  davar55  Puzzles  4  20070809 20:10 
Divisible by 7  davar55  Puzzles  3  20070514 22:05 