8
$\begingroup$

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.

$\endgroup$
16
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ How do I find out that the squares modulo 11 are 0,1,4,9,5,3? $\endgroup$ – Anil May 22 '17 at 12:41
  • 8
    $\begingroup$ 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}$. $\endgroup$ – Robert Z May 22 '17 at 12:42
  • $\begingroup$ Thank you, your answer helped me a lot. The alternating sum is the key point here $\endgroup$ – Anil May 22 '17 at 12:50
  • $\begingroup$ 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. $\endgroup$ – Robert Z May 22 '17 at 13:05
  • 1
    $\begingroup$ You could also use modulus 8.Then you'd only have to look at the last three digits. $\endgroup$ – Gerry Myerson May 22 '17 at 13:15
7
$\begingroup$

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$.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

I only suggest this because I enjoyed learning about this and quadratic reciprocity immensely in undergrad. :)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.