Problems & Puzzles: Problems

Problem 7.- Primes and Parity of x and its inverse x’, module p

For each x, such that 0<x<p, let’s define x’ as "the inverse of x" meaning that :

x . x’ = 1 (mod p)

Let Np be the number of cases in wich x and x’ are of opposite parity.

Example : for p=13, Np=6

(x, x’)={(2, 7), (5, 8), (6, 11), (7, 2), (8, 5), (11, 6)}

How often are x and x’ of "opposite parity" ? D. H. Lehmer invite us to find (a formula for) Np, or at least to say something not trivial about it.

(p. 251, Ref. 1)

Contribution came from Anton Vrba on March 2007:

Only by adding the condition 0<x*x<p^2 then the following answer can be given.

If p is prime but not a Mersenne or Fermat prime then there are exactly (p-1)/2 cases (and one less for Mersenne and Fermat primes) where t*p+1=2^r*q= 1 (mod p), t=1,2...p-1;   and we could say that q is the root-inverse of 2^r, r>0 and q odd.

As q can be factored into f1*f2*..fn then  f2*...fn is a derivative-inverse of  f1*2^n, and to complete the answer  the mirrors need to be considered

Example, for prime 17 there exist (17-1)/2-1=7 cases where the inverses of opposite parity are listed below, with the derivatives and mirrors.

1- (2,9) and derivative (6,3) and mirrors (3,6) (9,2)

2- (4,13) and mirror (13,4)

3- (2,43);

4- (8,15) and derivatives (5,24)(3,40), and mirror (15,8);

5- (2,77) and derivatives (14,11),(4,22) and mirror(11,14);  

6- (4,47) ;

7- {2,111) and derivatives (6,37), (3,34);

For the requirement that both 0<x<p and 0<x<p as the example of the problem implies, then the problem can only be analyzed by computational filtering the above result.

The surprising result of such computational filtering to the indicated parity and p prime is that for:-

whatever parity Np(all) = p-2 (exact relationship)

opposite parity, Np(op) ≈ p/2 (see graph)

even-even parity, Np(ee) ≈ p/4

odd-odd parity, Np(oo) = Np(ee)-1 (exact relationship)


1. Can you explain the fundamental theory behind the result?

2. How do you prove Np(all) = p-2 and  Np(oo) = Np(ee)-1 ?

2. Can you find counter examples?



Records   |  Conjectures  |  Problems  |  Puzzles