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)=r1pq mod r1=r2pq 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

***

 Records   |  Conjectures  |  Problems  |  Puzzles