MathDB

Let

n

be an odd integer and

m=\phi(n)

be the Euler's totient function. Call a set of residues

T=\{a_1, \cdots, a_k\} \pmod n

to be good if

\gcd(a_i, n) > 1

\forall i

, and

\gcd(a_i, a_j) = 1, \forall i \neq j

. Define the set

S_n

consisting of the residues

\sum_{i=1}^k a_i ^m\pmod{n}

over all possible residue sets

T=\{a_1,\cdots,a_k\}

that is good. Determine

|S_n|

.
Proposed by Anzo Teh Zhao Yang

Problem Statement