Squares modulo 7 and 10

-
This post was first published on WordPress at
https://explainingmaths.wordpress.com/2021/07/26/squares-modulo-7-and-10/

Here is yet another post from my Foundations of Pure Mathematics Piazza blog from Autumn 2020.

This time I was asked about squares modulo \(7\) and \(10\), along with a query about what a square modulo is. I think this confusion over what is being defined is because, in my definition of what it means for an integer \(m\) to be a square modulo \(k\), the maths doesn't come out in bold.

My response

Hi,
It isn't really ("square modulo") \(k\) it is more like "square (modulo \(k\))".
In fact, some authors define a function of \(n\) and \(k\) written
   \(n\) mod \(k\)
to mean the remainder (using the division algorithm) when you divide \(n\) by \(k\). (Try typing 19 mod 3 into Google! Also try -19 mod 3.) With this notation:

  • \(8\) mod \(3 = 2\), because the division algorithm gives \(8=2\times 3 + 2\); 
  • \(11\) mod \(4=3\), because the division algorithm gives \(11=2 \times 4 + 3\);
  • \(-7\) mod \(5=3\), because the division algorithm gives \(-7 = (-2) \times 5 + 3\).

Remember, the remainder must always be non-negative and strictly less than \(k\).
So \(n\) mod \(k\) is always an element of \(\{0,1,...,k-1\}\).

When looking at squares modulo \(k\) (or mod \(k\)) for some particular value of \(k\), we are really asking:
"What are the possible remainders when you divide \(n^2\) by \(k\), as \(n\) varies through \(\mathbb{Z}\)."
With the notation above , that means we are essentially asking which of the integers \(0,1,\dots,{k-1}\) are in the set \(\{n^2\,\textrm{mod}\,k\mid n \in \mathbb{Z}\}.\)
[This last is the set of all possible remainders when you divide squares of integers by \(k\).]

A few more things to note about this \(n\,\textrm{mod}\,k\) function. Let \(m,n,r \in \mathbb{Z}\) and let \(k \in \mathbb{N}\). Then:

  • \(r\,\textrm{mod}\,k = r \Leftrightarrow r \in \{0,1,\dots,{k-1}\}\);
  • \((n\,\textrm{mod}\,k)\,\textrm{mod}\,k = (n \,\textrm{mod}\,k)\);
  • \(m \equiv n~~(\textrm{mod}\ k) \Leftrightarrow (m \,\textrm{mod}\, k) = (n \,\textrm{mod}\,k)\).

The last of these says that \(m\) is congruent to \(n\) modulo \(k\) if and only if \(m\) and \(n\) leave the same remainder when divided by \(k\) using the division algorithm.
[I have included more brackets than necessary here to try to eliminate any ambiguity!]

Returning to your questions: we had some previous discussion of this material in earlier posts, so what I say next will be fairly similar.

  • First, remember that if \(m \equiv n\) (mod \(k\)) then \(m^2 \equiv n^2\) (mod \(k\)). This is why we really only need to check \(0^2,1^2, 2^2,\dots,(k-1)^2\) mod \(k\). All other squares will just repeat the same remainders we found here.
  • Also, because we are squaring, we can use the fact that, for all integers \(n\), we have
          \(n^2 = (-n)^2 \equiv (k-n)^2\) (mod \(k\)).
    So \(1^2 \equiv (k-1)^2\) (mod \(k\)), \(2^2 \equiv (k-2)^2\) (mod \(k\)), etc., and this leads to more repeats and further short cuts.

Now let's look at the usual tables of squares, checking more squares than necessary. We'll look at squares modulo \(7\) and modulo \(10\), using the \(n\) mod \(k\) function discussed above, except looking at \(n^2\) mod \(7\) and \(n^2\) mod \(10\).

\(n\) \(-2\) \(-1\) \(0\) \(1\) \(2\) \(3\) \(4\) \(5\) \(6\) \(7\) \(8\) \(9\) \(10\)
\(n^2\) \(4\) \(1\) \(0\) \(1\) \(4\) \(9\) \(16\) \(25\) \(36\) \(49\) \(64\) \(81\) \(100\)
\(n^2\) mod \(7\) \(4\) \(1\) \(0\) \(1\) \(4\) \(2\) \(2\) \(4\) \(1\) \(0\) \(1\) \(4\) \(2\)
\(n^2\) mod \(10\) \(4\) \(1\) \(0\) \(1\) \(4\) \(9\) \(6\) \(5\) \(6\) \(9\) \(4\) \(1\) \(0\)

Note that \(n^2\) mod \(10\) is just the last decimal digit of \(n^2\). This is because \(n^2\) is non-negative. (Negative integers are different. For example \((-2)\) mod \(10\) = \(8\).)

We see the usual repeating patterns. We also see that we only needed to check \(0^2,1^2,2^2,3^2\) mod \(7\) (the rest are repeats) and we only needed to check \(0^2,1^2,2^2,3^2,4^2,5^2\) mod \(10\) (the rest are repeats).
[We discussed the reasons for these repeats above and in the earlier posts.]

The conclusion?
The squares modulo \(7\) are \(0\), \(1\), \(2\) and \(4\), and not \(3\), \(5\) or \(6\).
[If asked, though, I would say that, e.g., \(23\) is a square modulo \(7\), because, modulo \(7\) we don't really distinguish between \(23\) and \(2\). This fits with the terminology used in the law of quadratic reciprocity mentioned in an earlier post.]
Similarly, the squares modulo \(10\) are \(0\), \(1\), \(4\), \(5\), \(6\) and \(9\) and not \(2\), \(3\), \(7\) or \(8\). This is better known as the fact that if you square an integer, the last decimal digit can only be \(0\), \(1\), \(4\), \(5\), \(6\) or \(9\).
[Note in the above that the usage of and and or in English and/or in maths can be a tricky issue!]

I hope that this helps!
Best wishes,
Dr Feinstein

Comments

Post a Comment

Popular posts from this blog

Sums and integration against counting measure: Part I

-
For other posts in this series, see https://explaining-maths.blogspot.com/search?q=Sums+and+integration+against+counting+measure In case the MathJax mathematics below does not display properly in your browser, I have made a PDF of the main article available via my  WordPress blog  at  https://explainingmaths.files.wordpress.com/2023/08/sums-and-integration-against-counting-measure_-part-i.pdf Note added 30/8/23: I'm not quite sure when I started to say "integration against a measure". I'm not alone, but I think that "integration with respect to a measure" is a lot more common! However, I don't want to change the titles of my latest 10 blog posts, so I'll leave it as it is. I'll probably change back to "integration   with respect to a measure" in future though! It has been a while since I wrote a mathematical post! Here I thought I would say something about Measure and Integration which is relevant to my research. For these posts I as
Read more

Discussion of the proof that the uniform norm really is a norm

-
In response to a request on Piazza, I gave a detailed proof that the uniform really is a norm, including some comments and warnings on possible pitfalls along the way. Here (essentially) is what I said. Let’s have a look at \(\|\cdot\|_\infty\) on the bounded, real-valued functions on \([0,1]\) (but you can also work with bounded functions on any non-empty set you like, and the same proof will work). We define \(\ell_\infty([0,1]) = \{f: f \textrm{ is a bounded, real-valued function on }[0,1]\,\}\,,\) and this is the set/space we will look at. So we set \(Y=\ell_\infty([0,1])\). Then you can check for yourselves that \(Y\) really is a vector space over \(\mathbb{R}\) (using the usual "pointwise" operations for functions). Note that the zero element in this vector space is the constant function \(0\) (from \([0,1]\) to \(\mathbb{R}\)), which I'll denote by \(\mathbf{0}\) here for clarity. (We also used \(Z\) for this function in one of the exercises.) I'll first give
Read more

Revisiting liminf and limsup

-
This post is also available in PDF form from my WordPress Blog at  https://explainingmaths.wordpress.com/2023/09/01/revisiting-liminf-and-limsup/ My recent series of posts about Fatou's Lemma for sums was aimed primarily at mathematics students at 3rd-year undergraduate level or above. So I think I should write a post more suitable for first-year undergraduate students. So I'm going to have another look at the topic of $\liminf$ and $\limsup$ for bounded sequences of real numbers (though most of what I say can be generalised to sequences, or even nets, of extended real numbers). I said quite a lot about this in a previous post on my WordPress blog in the post https://explainingmaths.wordpress.com/2009/01/10/an-application-of-absorption-to-teaching-lim-inf-and-lim-sup/ and there was a lot of discussion in the comments below the post. In particular, in those comments, I discussed the $\liminf$ and the $\limsup$ of some examples of sequences $(x_n)$, including the following exam
Read more