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