Last Digits In Base 18815

First, note that the units digit of a number in base $x$ is simply its remainder when divided by $x$ . The problem simply asks for the number of distinct cubic residues modulo $18815$ .

The key observation here is that all prime factors of $18815$ are $\equiv 2 \pmod{3}$ .

---

*Lemma: * If $x^3 \equiv y^3 \pmod{p}$ for some integers $x,y$ and a prime $p \equiv 2 \pmod{3}$ , then $x \equiv y \pmod{p}$ .

*Proof: * First, note that if $x \equiv 0 \pmod{p}$ , then $y^3 \equiv 0 \pmod{p} \implies y \equiv 0 \pmod{p}$ . Now let $x,y \not \equiv 0 \pmod{p}$ . Assume $x \neq y \pmod{p}$ , so $\gcd (p, x-y)=1$ and $p|x^3-y^3 \implies p|(x-y)(x^2+xy+y^2) \implies p|x^2+xy+y^2 \\ \implies \left( xy^{-1} \right) ^2 + \left( xy^{-1} \right) + 1 \equiv 0 \pmod{p} \implies \Phi_3 \left( xy^{-1} \right) \equiv 0 \pmod{p},$ where $\Phi_3$ is the third cyclotomic polynomial $\left( \Phi_3 (z) = z^2+z+1\right)$ . This implies either $p=3$ or $3|p-1$ , none of which is the case since $p \equiv 2 \pmod{3}$ . $\blacksquare$

---

By the lemma, modulo $p$ , the set $\left \{ 0^3, 1^3, 2^3, \cdots , (p-1)^3 \right \}$ is equivalent to $\{0, 1, 2, \cdots , p-1 \}$ modulo $p$ whenever $p$ is a prime and $p \equiv 2 \pmod{3}$ , so the number of cubic residues modulo $p$ is $p$ . Thus, modulo $5, 53, 71,$ the number of cubic residues are $5, 53, 71$ respectively.

Now, we have to find the number of cubic residues modulo $18815$ . Let $a_i, b_i, c_i$ be any three cubic residues modulo $5, 53, 71$ respectively. Let $x^3$ be an arbitrary cube. Consider the congruency system $\begin{array}{lcl} x^3 \equiv a_i \pmod{5} \\ x^3 \equiv b_i \pmod{53} \\ x^3 \equiv c_i \pmod{71}. \end{array}$ By CRT, each of these congruency systems give rise to a unique solution modulo $18815$ . Conversely, for any cubic residue $r$ modulo $18815$ , there exist unique $a_i, b_i, c_i$ such that whenever $x^3$ is a solution to the above congruency, $x^3 \equiv r \pmod{18815}$ . Since $a_i, b_i, c_i$ can take $5, 53, 71$ values respectively, the number of cubic residues modulo $18815$ is $5 \times 53 \times 71= 18815$ , whose last three digits in decimal base are $\boxed{815}$ .

---

This problem was inspired by v_Enhance's solution to Iran TST 2013 Set 1 Day 2 Problem 5 .

java code:

public class brilliant201409091631{
    public static void main(String[] args){
        boolean[] occur = new boolean[18815];
        int count = 0;
        for(int i=0;i<18815;i++){
            occur[(i*i%18815)*i%18815] = true;
        }
        for(int i=0;i<18815;i++){
            if(occur[i]==true) count++;
        }
        System.out.println(count);
    }
}

output:

18815
Press any key to continue . . .