KöMaL 2020 A773

Let $b \ge 3$ be a positive integer and let $\sigma$ be a nonidentity permutation of the set $\{0, 1, \ldots, b - 1\}$ such that $\sigma(0) = 0$. The substitution cipher $C_\sigma$ encrypts every positive integer $n$ by replacing each digit $a$ in the representation of $n$ in base $b$ with $\sigma(a)$. Let $d$ be any positive integer such that $b$ does not divide $d$. We say that $C_\sigma$ complies with $d$ if $C_\sigma$ maps every multiple of $d$ onto a multiple of $d$, and we say that $d$ is cryptic if there is some $C_\sigma$ such that $C_\sigma$ complies with $d$. Let $k$ be any positive integer, and let $p = 2^k + 1$. $a)$ Find the greatest power of $2$ that is cryptic in base $2p$, and prove that there is only one substitution cipher that complies with it. $b)$ Find the greatest power of $p$ that is cryptic in base $2p$, and prove that there is only one substitution cipher that complies with it. $c)$ Suppose, furthermore, that $p$ is a prime number. Find the greatest cryptic positive integer in base $2p$, and prove that there is only one substitution cipher that complies with it.