A001915, A001916, modular numbers, and remainders

[David W. Wilson]

A001915 and A001915 were taken from a 1924 number theory manuscript.
As of 12/2000, the EIS description was something like "Solution to a
modular equation".  On 12/12/2000, Joe Crump posted a math-fun note
saying that he had found that A001915 appeared to be a list of primes
for which 2^p == 3 (mod p) was soluble.  Shortly thereafter, I noted
that A001916 appeared to be a list of primes for which 2^p == 5 (mod p)
was soluble.

It is notable, however, that each of A001915 and A001916 omits the
value 2, which in each satisfies the proposed congruences.  Certainly
2 was universally recognized as a prime number in 1924, so one can only
speculate on why 2 was omitted from each sequence.  Maybe the author
was interested only in odd primes, or possibly it may be related to
a subtle difference between modular numbers and remainders.

If a is an integer and m a positive integer, there exist a unique pair
of integers (q, r) satisfying

    0 <= r < a
    a = mq+r

q and r are called, respectively the integer quotient and remainder of
a and m, and satisfy

    q = a div m = [a/m]
    r = a mod m = a - mq

where [x] is the floor function.  Note that a mod m is a mapping from
Z X Z+ to Z.

On the other hand, when we say

    a == b (mod m)

(In print, == is the congruence sign, written as three horizontal
bars).  Mathematicians interpret this to mean that a and b are equal
elements of Z/mZ.  However, in computing contexts (especially, when
programming in languages which do not explicitly support modular
integers) we interpret the above to mean that a and b are integers with
a mod m = b mod m, (which is probably closer to what Gauss thought).

The subtle difference between modular numbers and remainders I would
like to point out is that

   a == b (mod m)

is not equivalent to

   a == b mod m

Specifically, the former makes no restrictions on a as an integer,
while the latter requires 0 <= a < m.  In programming environments,
failure to notice this can lead to missed or extraneous solutions to
modular identities.

Such is the case with of A001915.  It's current description is

%N A001915 Primes p such that the congruence 2^x = 3 (mod p) is solvable.

This description requires 2 to be in the sequence, since 2^1 == 3 (mod 2).
However, the description

%N A001915 Primes p such that 2^x mod p = 3 is solvable.

describes the sequence as it stands, since 2^x mod 2 (the remainder on
dividing 2^x by 2) must be 0 or 1, and hence can never be 3.

%N A001916 Odd primes p such that the congruence 2^x = 3 (mod p) is solvable.

also fixes the problem.

So, we should either add 2 to the sequence or fix the description.