MathDB

Let

b\geq 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

C_\sigma

maps every multiple of

d

onto a multiple of

d,

and we say that

d

is cryptic if there exists 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 complying with it.
b) Find the greatest power of

p

that is cryptic in base

2p,

and prove that there is only one substitution cipher complying 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.
Proposed by Nikolai Beluhov, Bulgaria

A. 773