[BOJ 15174] Hilbert’s Hash Browns

$\newcommand{\Z}{\mathbb{Z}}$

$\newcommand{\N}{\mathbb{N}}$

$\newcommand{\gang}[1]{\langle #1 \rangle}$

We have to calculate the number of the possible value form of $x^{p}+q \pmod{n}$.

Lemma 1. There exists a bijection between $\{x^{p}+q\pmod{n}\}$ and $\{x^{p}\pmod{n}\}$.

Proof. For convenience, let each set be $A,B$ resp. Construct a map $\phi:A\rightarrow B$ with $\phi(\overline{a})=\overline{a-q}$.(Note that $\overline{x}$ denotes the image of $x$ modulo $n$.) Assume $\overline{\phi(a)}= \overline{\phi(b)}$. Then $\overline{a-q}= \overline{b-q} \implies \overline{a}= \overline{b}$. $\phi$ is injective. Take $\overline{a}\in B$. It means for some $\overline{x}$,  $\overline{x^{p}} =\overline{a}$. It gives $\overline{a+q}$ as the preimage of $a$. $\blacksquare$

 

Lemma 2. Let $q$ be an odd prime, $k,p\in\N$. Let $d:=\gcd(p,\varphi(q^{k}))$. There is exactly $\frac{\varphi(q^{k})}{d}$ distinct values of $\overline{x^{p}}\in (\Z/q^{k}\Z)^{\times}$

Proof. Let $G:=(\Z/q^{k}\Z)^{\times}$. Consider a group homomorphism $f:G\rightarrow G$ with $f(x)=x^{p}$. Consider $\ker(f)=\{x\in G|x^{p}\equiv 1\pmod{q^{k}}\}$. There exists primitive root $g$ of $q^{k}$ such that $g^{s}\equiv x\pmod{q^{k}}$ for some $1\le s\le \varphi(q^{k})$. On condition on kernel, $g^{sp}\equiv 1\pmod{q^{k}}\implies \varphi(q^{k})|sp$. Then $\frac{\varphi(q^{k})}{d}|s$. From the restriction of $s$, there exist $d$ values of $s$ that make $x$ in the kernel. i.e. $|\ker(f)|=d$. By the first isomorphism theorem, $G/\ker(f)\cong \text{Im}(f)$. It gives $\frac{|G|}{|\ker(f)|}=|\text{Im}(f)|\implies |\text{Im}(f)|=\frac{\varphi(q^{k})}{d}$. $\blacksquare$

 

Lemma 2 holds for $q=2$ with $k\le 2$ since these numbers have a primitive root.

 

Lemma 3. Let $k\in N_{\ge 3}$. $5$ has an order $2^{k-2}$ in $(\Z/2^{k}\Z)^{\times}$. Furthermore, powers of $5$ permute the number of form $4n+1$ in $(\Z/2^{k}\Z)^{\times}$.

Proof. Use binomial expansion, $(1+2^{2})^{2^{k-2}}\equiv \sum_{i=0}^{2^{k-2}}{2^{k-2}\choose i}2^{2i}\equiv 1+2^{k-2}2^{2}\equiv 1\pmod{2^{k}}$. By Lagrange theorem, order of $5$ divides the $\varphi(2^{k})=2^{k-1}$. Thus it suffices to prove that $2^{k-3}$ is not an order of $5$. Again, $(1+2^{2})^{2^{k-3}}\equiv \sum_{i=0}^{2^{k-2}}{2^{k-2}\choose i}2^{2i}\equiv 1+2^{k-3}2^{2}+\frac{2^{k-3}(2^{k-3}-1)}{2}2^{4}\equiv 1+2^{k-1}\not\equiv 1\pmod{2^{k}}$. There exists $2^{k-2}$ numbers of the form $4n+1$. Since $5^{k}\equiv 1\pmod{4}$ and they are distinct, $5$ permutes the $4n+1$. $\blacksquare$

 

Lemma 4. Let $k\in\N_{\ge 3}$. If $p$ is odd, there exists $2^{k-1}$ distinct value and if $p$ is even, define $d:=\gcd(p,2^{p-2})$, there exists $\frac{2^{k-2}}{d}$ distinct value of $x^{p}\pmod{2^{k}}$. 

Proof. Consider a homomorphism $f:\gang{\overline{5}}\rightarrow \gang{\overline{5}}$ with $f(x)=x^{p}$. $\ker(f)=\{x\in\gang{\overline{5}}|x^{p}\equiv 1\pmod{2^{k}}\}$. Kernel condition implies $5^{sp}\equiv 1\pmod{2^{k}}$ for some $1\le s\le 2^{k-2}$ and gives $2^{k-2}|sp\implies \frac{2^{k-2}}{d}|s$. There are only $d$ values of $s$ satisfying that condition. Thus, $|\ker(f)|=d$. By the first isomorphism theorem, $\gang{\overline{5}}/\ker(f)\cong \text{Im}(f)$. Thus, $|\text{Im}(f)|=\frac{2^{k-2}}{d}$. Consider when $p$ is odd. Take $a,b\in (\Z/2^{k}\Z)^{\times}$. Assume $a^{p}\equiv b^{p}\pmod{2^{k}}$. Then $\frac{a}{b}^{p}\equiv 1\pmod{2^{k}}$. Unless $a=b$, the order of $\frac{a}{b}$ is greater than $1$. So, the order would be the power of $2$. But since $p$ is odd, this is a contradiction. Hence, there are $2^{k-1}$ distinct value of $x^{p}\pmod{2^{k}}$ in $(\Z/2^{k}\Z)^{\times}$. Assume $p$ is even. We want to examine the tendency of the number form of $4n+3$ power of $p$. Take $0\le n< 2^{k-2}$. Then $(4n+1)^{p}\equiv (4(2^{k-2}-n)-1)^{p}\pmod{2^{k}}$ holds. Let $p=2m$ for some $m\in\N$. Then $(4(2^{k-2}-n)-1)^{2m}\equiv (16n^{2}+8n+1)^{m}\equiv (4n+1)^{p}\pmod{2^{k}}$. It means powers of $4n+3$ immediately coincide with powers of $4n+1$. Thus, there exists only $\frac{2^{k-2}}{d}$ distinct value. $\blacksquare$

 

We search for a distinct value of power in the units of the modulo. So, we have to check for non-unit numbers. The idea is simple. Assume $p\ge k$. Then the power to the $p$ of numbers which are multiples of $q$ shrink into $0$. Then just add $1$ and we are done. Assume $p<k$. Divide every number $q^{p}$. Then the problem is reduced into find distinct values on $\Z/q^{k-p}\Z$. This makes the problem a "recurrence". 

We have done on the prime powers. By using CRT, we can make it for the arbitrary $n$.