Project Euler Problem 817
Define m = M(n, d) to be the smallest positive integer such that when m^2 is written in base n it includes the base n di
Solution
Answer: <NUMBER>
Let $t=p-d$. We are looking for the smallest positive integer $m$ such that some base-$p$ digit of $m^2$ equals $t$.
For $m<p$, the base-$p$ expansion of $m^2$ has at most two digits:
$$m^2 = ap+b,\qquad 0\le b<p.$$
So the digit $t$ appears iff either
- $b=t$, i.e. $m^2\equiv t\pmod p$, or
- $a=t$, i.e.
$$tp \le m^2 < (t+1)p.$$
For the actual problem,
$$p=10^9+7\equiv 3\pmod 4,$$
so modular square roots are easy:
$$x^2\equiv -d \pmod p \iff x\equiv \pm (-d)^{(p+1)/4}\pmod p.$$
For each $d=1,\dots,10^5$, one computes:
- the least positive root of
$$x^2\equiv -d \pmod p$$
when $-d$ is a quadratic residue; 2. otherwise, the least integer $m$ such that
$$(p-d)p \le m^2 < (p-d+1)p.$$
Summing all resulting minimal values gives
$$\boxed{226427929440}$$
Therefore,
Answer: 226427929440