# How to show that a large given integer isn't a square number by using mod?

Given a big integer like $4531893869$ the question is how to show that this number isn't a square number using mod $11$.

Basically what we have is something like that: $$4531893869 \equiv x \pmod{11}$$ and we know that $x \in \{1\ldots10\}$.

According to Wolfram Alpha the result is $8$.

But I don't understand how this will show us that this large number isn't a square number. I have to explicitly use mod $11$ to solve this task but I don't understand the mathematical context.

Hint. The squares modulo 11 are $0,1,4,9,5,3$. Since $10^k\equiv (-1)^k \pmod{11}$ it follows that the number $4531893869$ modulo $11$ can be obtained by computing: $$-4+5-3+1-8+9-3+8-6+9\pmod{11}.$$ If it does not belong to $\{0,1,4,9,5,3\}$ then $4531893869$ can not be a square modulo 11 and therefore it is not a perfect square.

• How do I find out that the squares modulo 11 are 0,1,4,9,5,3?
– Anil
May 22 '17 at 12:41
• Just compute $j^2\pmod{11}$ for $j=0,\dots, 10$. Actually $j=0,\dots, 5$ is enough because $j^2\equiv (11-j)^2\pmod{11}$. May 22 '17 at 12:42
• Thank you, your answer helped me a lot. The alternating sum is the key point here
– Anil
May 22 '17 at 12:50
• Yes. Note that in this case you could replace 11 by 3. $4531893869\equiv 2\pmod{3}$ (here you consider the sum of the digits since $10\equiv 1\pmod{3}$) and $2$ is not a square modulo 3. May 22 '17 at 13:05
• You could also use modulus 8.Then you'd only have to look at the last three digits. May 22 '17 at 13:15

The key point is that not every value mod $11$ can be a square. In fact for any square $n^2$, $n$ must be congruent to one of $0,1,...,10$ mod $11$, and so $n^2$ must be congruent to one of $0^2,1^2,...,10^2$ mod $11$. So as long as none of $0^2,1^2,...,10^2$ is congruent to $8$ mod $11$, there are no squares congruent to $8$ mod $11$, and your number can't be square.

In fact you can save yourself some work here: $10\equiv -1$ mod $11$, so $10^2\equiv(-1)^2=1^2$, so once you've checked $1^2$ you don't need to check $10^2$. Similarly with other pairs of numbers which have sum $11$, so in fact it is sufficient to check none of $0^2,1^2,...,5^2$ is congruent to $8$ mod $11$.

Hint $\ {\rm mod}\ 11\!:\ n^{\large 2}\equiv 2^{\large 3}\equiv x\$ when raised to $\color{#c00}5$'th power contradicts little Fermat, viz.

$\quad\overset{(\ \ \ )^{\Large\color{#c00} 5}}\Longrightarrow\,\ \underbrace{ 1\equiv (n^{\large 2})^{\large\color{#c00} 5}}_{\rm Fermat}\!\equiv (2^{\large 3})^{\large\color{#c00} 5}\equiv (2^{\large 5})^{\large 3}\equiv (-1)^{\large 3}\equiv -1,\$ but $\,\ 1\not\equiv -1\pmod{\!11}$

Remark  This method of square testing works generally - see Euler's criterion. It is much more efficient than brute-force enumerative tests for larger numbers.

Generally we can disprove equalities of integer arithmetical expressions by checking that they are not congruent modulo $m$. This works because modular reduction is compatible with addition and multiplication (see the Congruence Sum and Product Rules), so it preserves equalities (as congruences) between integer expressions composed of sums and products, i.e. polynomial expressions of integers, e.g. $$P(i,j,k) = Q(i,j,k) \ \Rightarrow\ P(i,j,k)\equiv Q(i,j,k)\pmod m$$

for any polynomials $P,Q$ with integer coefficients. So if the congruence fails for some modulus $m$ then the LHS equality must also fail.

I recognize that this is complete overkill for a problem as rudimentary as this, but another method to tell if $4531893869$ is quadratic residue$\pmod{11}$ is to use the Legendre symbol: https://en.m.wikipedia.org/wiki/Legendre_symbol

\begin{align} \left( 4531893869 / 11 \right) & \equiv 4531893869^{\frac{11-1}{2}}\pmod {11} \\ & \equiv 8^{\frac{11-1}{2}} \\& \equiv -1 \end{align}

So, no. It is not.