Problems & Puzzles: Puzzles

Puzzle 910. Follow up to Puzzle 908 In the Puzzle 908 we deal with an algorithm that starting with two given primes (p, q), k residues r are generated by the the following scheme: Given (p, q), let pq = p*q pq mod (p+q)=r1 pq mod r1=r2 pq mod r2=r3 ... pq mod rk-1= rk =1 (stop) or in a compact form: (p, q)-> {r1, r2, ...rk}, rk=1 As you can see I supposed incorrectly that always at the end some k residue value is 1. Emmanuel Vantieghem was the only that noticed and reported this mistake and give a some counter examples: ( 2, 7 )  ->  {5, 4, 2, 0} ( 3, 11 )  ->  {5, 3, 0} ( 7, 23 )  ->  {11, 7, 0} Please notice that in these three examples the residue value 1 is never attained but two "last" residues: p & 0. Emmanuel added this comment: I even think that for every prime  p  there exists a prime  q > p  such that  ( p, q )  ->  { ... , p , 0}.  But of course, this will be difficult to settle. Q1. Can you get a proof of the Emmanuel's conjectural statement: for every prime  p  there exists a prime  q > p  such that  ( p, q )  ->  { ... , p , 0} ? Q2. If Q1 is not available easily, please find all these p prime values such that q is not found inside certain wide range defined by yourself.

---

Contribution came from Emmanuel Vantieghem

***

Emmanuel wrote on Feb-1-2018:

The conjecture is true !
 

I came to this by close observation of the set  {r1, r2, ... ,rl}  for a fixed  p (not too big)  and  q = p+1, p+2, ...

For instance, when  p = 7, tabulating  q,  the residue sets  I got : 

  8, {11, 1}

  9, {15, 3, 0}

  ...

  336,  {294, 0}

  337,  {295, 294, 7, 0}

  338,  {296, 294, 14, 0}

  339,  {297, 294, 21, 0}

  340,  {298, 294, 28, 0}

  341,  {299, 294, 35, 7, 0}

  342,  {300, 294, 42, 0}

  343,  {301, 294, 49, 0}

  344,  {302, 294, 56, 0}

  ...

The last residue seemed to be always zero from 336 (= 7^3 - 7) on.

This was sufficient to me to see that it should be possible to find a proof of the following :

 

For every prime  p  and every natural number  q  >  p^3 - p, the residue scheme ends in zero.

 

This is indeed easy to prove as follows :

   Write  q  as  p^3 - p + k  (for  k > 0)

   Then, p + q = p^3 + k  so that we have :

      p q === p (p^3 - p + k) === -p^2 === p^3 + k - p^2 (mod p+q )

   Thus, r1 = p^3 - p^2 + k (mod p+q).

   Next, in order to compute  r2, we have modulo r1 :

     p q === p^3 - p^2  (mod  p^3 - p^2 + k)  (proof left to the reader).

   Hence, r2  is independent of  k.

   Furthermore, r2  is clearly divisible by  p  and hence all further residue  ri (i >= 2) will be divisible by  p.

   This means that none of the residue can be 1, QED.

 

A consequence of this it that for every prime  p  there is a greatest  q  such that the last residue is 1

***

---