Tough number theory problem

[Larry Hammick]

Prove that if p is a prime and p = 8n+3 for some natural number n,
then the set
{1, 2, ..., 2n}
contains exactly n squares mod p. (V.-A. Lebesgue, 1842)

[billh04]

I found your paper "On squares modulo a prime 8n + 3" on the web which
gives your solution. I will be working on other things (not math) for
the time being, so I want to record some things related to this
problem and your paper.

One notes quickly that 2 and -1 are not squares modulo p. But, this is
not sufficient to carry the proof through.

Your paper considers the number of squares in the set {2, 4, ..., 4n}
which is equivalent to the problem posed here. Your paper suggests to
start with the square 1 and multiply it by 2 continually. The element
1*2^x will be in that orbit. You define the following four sets:

1) A is the set of 2^x where x is even and 2^x is big and odd
2) B is the set of 2^x where x is even and 2^x is small and even
3) C is the set of 2^x where x is odd and 2^x is big and odd
4) D is the set of 2^x where x is odd and 2^x is small and even

I want to define the following sets:

5) S1 is the set of 2^x where x is even and 2^x is small and odd
6) S2 is the set of 2^x where x is odd and 2^x is small and odd
7) S3 is the set of 2^x where x is even and 2^x is big & even
8) S4 is the set of 2^x where x is odd and 2^x is big & even.

The problem is to show that B has n elements.

Note that multiplication by -1 takes A to D, D to A, B to C, and C to
B.

Note that multiplication by 2 takes A to C or S2.
Note that multiplication by 2 takes B to D or S4.
Note that multiplication by 2 takes C to A or S1.
Note that multiplication by 2 takes D to B or S3.
Note that multiplication by 2 takes S1 to S4 or D.
Note that multiplication by 2 takes S2 to S3 or B.
Note that multiplication by 2 takes S3 to S2 or C.
Note that multiplication by 2 takes S4 to S1 or A.

The idea in your paper is to eliminate from the orbit the (small and
odd) and (big and even). That is, you eliminate the elements in the
S's. You then take the first two and last two elements of the orbit
and show that they belong to A,B,C,D in some order. You repeat for the
third and fourth element from the front and back of the orbit, etc.
This shows that B has n elements.

In order to show that the four elements chosen belong to A,B,C,D in
some order you introduce the function f etc.

I tried another approach using the above eight sets. The idea is that
the first element chosen must belong to A, B, C, or D. Thus there are
four cases to consider. Take the case where the element belongs to A.
Then the second element is obtained by multiplying by 2 successively,
ignoring elements in the S's until we get an element not in the S's.
But, multiplying by 2 an element of A will yield an element of C or
S2. If we got C, then we stop. If we got S2, we multiply by 2 and
obtain an element in B or S3. If we got S3, we multiply by 2 and
obtain an element in C or S2. In general, we see that starting with an
element of A, multiplication by 2 will yield an element of B or C. But
the mirror images of these elements on the opposite side of the orbit
(obtained by multiplying by -1) will then be D and C or B.
Thus, starting with an element of A, we obtain one element each from
A,B,C,D as we claimed.

Of course, the orbit may not be all of the elements in A,B,C,D. If
not, we repeat the above for each distinct orbit.

The above has more tedious cases to plow through than the paper by
Larry Hammick. However, I was trying to avoid the "f" function which
didn't seem like an obvious approach to handle the problem. One would
like to be able to pair each low even square with a low even non-
square.

As an aside, I was looking at the following for the cases p = 19 and p
= 43. Let's take the case p = 19. Write the following table:

1 2 4 8 16
3 6 12
5 10
7 14
9 18
11
13
15
17

Since 2 and -1 are not squares, it is immediate that 1, 4, 16 are
squares and 18, 15, and 3 are non-squares. I circle these squares and
underline these non-squares. It is also immediate that 2 and 8 are non-
squares and 17 and 11 are squares. Underline and circle them.

It follows that 6 is a square and 12 is a non-square, and 13 is a non-
square and 7 is a square. Circle and underline.

It follows that 14 is a non-square and 5 is a square. Circle and
underline.

It follows that 10 is a non-square and 9 is a square. Circle and
underline.

Done.

I would suspect that for any p = 8n + 3 the above circling and
underlining will always exhaust all the numbers.

Bill Hale

[Larry Hammick]

On Sep 13, 6:55 pm, billh04 <h...@tulane.edu> wrote:
> On Sep 1, 7:40 am, Larry Hammick <larryhamm...@telus.net> wrote:
>
> > Prove that if p is a prime and p = 8n+3 for some natural number n,
> > then the set
> > {1, 2, ..., 2n}
> > contains exactly n squares mod p. (V.-A. Lebesgue, 1842)
>
> I found your paper "On squares modulo a prime 8n + 3" on the web which
> gives your solution.

I copied it to this group's webspace. The filename is bigsmall.pdf.

I haven't seen V.-A. Lebesgue's paper. I got the reference from
somebody else. I'm curious, does it use analytic methods? Dirichlet's
analytic class number formula and similar things were fashionable
after the appearance of his famous paper of 1837 about arithmetic
progressions. TIA.