Possible remainders of a square

First note that in base $10$ , finding the $X$ possibilities for the units digit is the same thing as finding the number of quadratic residues modulo $10$ . Similarly, finding the $X$ possibilities for the units digit in base $N$ is the same as finding the number of quadratic residues modulo $N$ . Now since $N=3 \cdot 5 \cdot 7 \cdot 11 \cdot 13$ , this is equivalent to the product of the number of quadratic residues in modulo $3,5,7,11$ and $13$ by the Chinese Remainder Theorem. It is well known that the number of quadratic residues mod $p$ is simply $\frac{p+1}{2}$ , so $X=\displaystyle \prod_{p=3,5,7,11,13} \frac{p+1}{2}=1008 \equiv \boxed{008} \pmod{1000}$

Number theory approach: Note that the question is asking for the possibilities of remainder when a perfect square is divided by N.

• There are 2 possibilities of the remainder when a perfect square is divided by 3.
• 3 when by 5.
• 4 when by 7.
• 6 when by 11.
• 7 when by 13.

Therefore the answer is 2x3x4x6x7=1008.

---

Programming approach:

java code:

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

output:

1008
Press any key to continue . . .

Here note that the unit digit of the perfect square a^2 written in base N is just the remainder when a^2 is divided by N. Now, let A be the set of the possible remainders when a perfect square is divided by N. And let A {3}, A {5}, A {7}, A {11} and A {13} be the sets of the possible remainders when a perfect square is divided by 3, 5, 7, 11 and 13 respectively. Let B a set that is equal to A 3 \times A 5 \times A 7 \times A {11} \times A {13}. Now, the crux move is that you can get a one-to-one correspondence between the sets A and B. The possible remainders when a perfect square is divided by 3, 5, 7, 11 and 13 are 2, 3, 4, 6 and 7. So, the number of elements in B is 2 \times 3 \times 4 \times 6 \times 7 which is also the number of elements in A. So A has got 1008 elements and consequently the correct answer would be 008.