1
$\begingroup$

How to find the smallest $p,q\in\mathbb N$ such that the following expression gives a periodic sequence of $a$ ODD numbers and $b$ EVEN numbers? ($n=0,1,2,\dots$) $$ S(n)=p^n\bmod q$$


Some examples below, written as "$(a,b) : p \space q \space\space\space\space s$", where $s(n)=S(n)\bmod2$

(1,1) : 2 3      [1, 0]
(1,2) : 2 7      [1, 0, 0]
(1,3) : 2 15     [1, 0, 0, 0]
(1,4) : 2 31     [1, 0, 0, 0, 0]
(1,5) : 2 63     [1, 0, 0, 0, 0, 0]
(2,1) : 7 9      [1, 1, 0]
(2,2) : 3 5      [1, 1, 0, 0]
(2,3) : 37 41    [1, 1, 0, 0, 0]
(2,4) : 11 21    [1, 1, 0, 0, 0, 0]
(2,5) : 89 111   [1, 1, 0, 0, 0, 0, 0]
(3,1) : 3 19     [1, 1, 1, 0]
(3,2) : 11 25    [1, 1, 1, 0, 0]
(3,3) : 5 9      [1, 1, 1, 0, 0, 0]
(3,4) : 45 71    [1, 1, 1, 0, 0, 0, 0]
(3,5) : 53 153   [1, 1, 1, 0, 0, 0, 0, 0]
(4,1) : 3 11     [1, 1, 1, 1, 0]
(4,2) : 9 35     [1, 1, 1, 1, 0, 0]
(4,3) : 15 49    [1, 1, 1, 1, 0, 0, 0]
(4,4) : 9 17     [1, 1, 1, 1, 0, 0, 0, 0]
(4,5) : 9 259    [1, 1, 1, 1, 0, 0, 0, 0, 0]
(5,1) : 31 57    [1, 1, 1, 1, 1, 0]
(5,2) : 11 43    [1, 1, 1, 1, 1, 0, 0]
(5,3) : 165 203  [1, 1, 1, 1, 1, 0, 0, 0]
(5,4) : 19 81    [1, 1, 1, 1, 1, 0, 0, 0, 0]
(5,5) : 19 25    [1, 1, 1, 1, 1, 0, 0, 0, 0, 0]


The examples were searched for by brute force.
How can one find the solutions directly, or in the most efficient way?

Will there always be solutions for every $a,b$ ?

The only pattern I know of so far is the most trivial one: $(1,b) : p,q=2,2^{b+1} - 1$

$\endgroup$
  • 1
    $\begingroup$ $a+b$ must be a factor of Carmichael lambda of $q$, and $\gcd(p, q) = 1$. Also, $p$ must be odd for $a>1$. Just my observation. $\endgroup$ – user202729 Jan 16 '18 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.