Divisible by a Prime

[davar55]

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).

[akruppa]

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

[Kevin]

All you did was restate the problem. The puzzle is to prove that theorem (or at least one direction of it).

[R.D. Silverman]

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.

[davar55]

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.)

[mfgoode]

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

[Zeta-Flux]

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.

[akruppa]

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

[Zeta-Flux]

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.

[davar55]

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]

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