Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
 Already signed up? New to KöMaL?

# Problem A. 773. (March 2020)

A. 773. Let $\displaystyle b \ge 3$ be a positive integer and let $\displaystyle \sigma$ be a nonidentity permutation of the set $\displaystyle \{0, 1, \ldots, b - 1\}$ such that $\displaystyle \sigma(0) = 0$. The substitution cipher $\displaystyle C_\sigma$ encrypts every positive integer $\displaystyle n$ by replacing each digit $\displaystyle a$ in the representation of $\displaystyle n$ in base $\displaystyle b$ with $\displaystyle \sigma(a)$. Let $\displaystyle d$ be any positive integer such that $\displaystyle b$ does not divide $\displaystyle d$. We say that $\displaystyle C_\sigma$ complies with $\displaystyle d$ if $\displaystyle C_\sigma$ maps every multiple of $\displaystyle d$ onto a multiple of $\displaystyle d$, and we say that $\displaystyle d$ is cryptic if there is some $\displaystyle C_\sigma$ such that $\displaystyle C_\sigma$ complies with $\displaystyle d$.

Let $\displaystyle k$ be any positive integer, and let $\displaystyle p = 2^k + 1$.

$\displaystyle a)$ Find the greatest power of $\displaystyle 2$ that is cryptic in base $\displaystyle 2p$, and prove that there is only one substitution cipher that complies with it.

$\displaystyle b)$ Find the greatest power of $\displaystyle p$ that is cryptic in base $\displaystyle 2p$, and prove that there is only one substitution cipher that complies with it.

$\displaystyle c)$ Suppose, furthermore, that $\displaystyle p$ is a prime number. Find the greatest cryptic positive integer in base $\displaystyle 2p$, and prove that there is only one substitution cipher that complies with it.

Submitted by Nikolai Beluhov, Bulgaria

(7 pont)

Deadline expired on April 14, 2020.

### Statistics:

 2 students sent a solution. 7 points: Weisz Máté. 5 points: 1 student.

Problems in Mathematics of KöMaL, March 2020