What the best way to introduce congruences in a number theory course? I am looking for something which will have an impact. What are the really interesting applications of congruent mathematics?
$\begingroup$
$\endgroup$
5
-
4$\begingroup$ Computing the day of the week of any given day in the history of life itself. $\endgroup$– Git GudCommented Sep 14, 2013 at 22:10
-
$\begingroup$ Burton's book has very nice examples. $\endgroup$– Pedro ♦Commented Sep 14, 2013 at 22:30
-
3$\begingroup$ I typically start by asking what day will be (tomorrow, in 3 days, as warmup and then) in 7,000,000,001 days.. As they typically figure the answer immediately, that is very good starting point to introduce the idea of modular arithmetic. $\endgroup$– N. S.Commented Sep 14, 2013 at 22:36
-
$\begingroup$ @N.S.: I've never heard that approach before, it's excellent. $\endgroup$– Michael AlbaneseCommented Sep 14, 2013 at 22:47
-
$\begingroup$ Thanks. Will try the clock example. $\endgroup$– user92877Commented Sep 15, 2013 at 11:32
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
3
What I find works with students is to hand them a problem they completely understand the meaning of and ask them to solve it. Before telling them anything about congruences, give them a couple of simple number theory problems to solve, which are hard to do without congruences. A brief excursion online produced these two -- there are thousands of others of course, you could pick anything that appeals to you.
Show that 3 divides $4^n -1$ for all integers n.
Show that $n^5 - n$ is divisible by 3 for all integers n.
Let them try to prove these things (or whatever you pick; these may be too easy). Then show them that there is an easier way. But first, of course, you have to introduce an idea. They may still squirm around while you are introducing congruences, but they'll come back to life when you start proving those problems.
-
$\begingroup$ Diophantine equations are good for this as well. Show that $x^2 - 3y^2 = 2$ has no integer solutions. $\endgroup$ Commented Sep 14, 2013 at 23:01
-
$\begingroup$ Thanks for this. I find this useful. $\endgroup$ Commented Sep 15, 2013 at 11:32
-
$\begingroup$ The first problem is easy to solve with recurrence $\endgroup$– QuadeCommented May 19, 2020 at 21:33
$\begingroup$
$\endgroup$
3
Well, it's sometimes referred to as clock arithmetic and introduced using the idea that the a.m./p.m. time can be deduced from the $24$ hour time using $\operatorname{mod} 12$. This may be helpful, but to me it seems a bit too far from modular arithmetic itself; one difference is that times are usually not expressed by a whole number (unless it just so happens to be on the hour), whereas modular arithmetic deals with integers (both positive and negative). Furthermore, there are infinitely many integers congruent to one another modulo any number; this fact is not reflected in the clock example. Just to be clear, I'm not saying that using the $24$ hour time as part of an introduction to the subject is bad, I just don't think it should be the only motivation/example before moving on to the abstract language of modular arithmetic.
Another idea you could use is to do some simple exercises with even and odd numbers. The types of exercises I'm referring to are the ones where you use the fact that a number is even/odd to write it as $2k$/$2k+1$. Then point out that the only thing that makes any difference throughout is whether the number is $2k + {\bf 0}$ or $2k + {\bf 1}$ (in particular, it doesn't matter what $k$ is, only that it is an integer) so why not just keep track of whether it is a zero or a one? Alternatively, if it doesn't matter what $k$ is, we consider $k = 0$ because that's simplest. You could then introduce $\operatorname{mod} 2$ as the notation you use when you choose to forget about $k$ (or set it to zero). From there you can discuss what $\operatorname{mod} 2$ means mathematically, as well as introducing $\equiv$. Once you have the mathematical description, it is clear that there is nothing special about $2$, so you could use any positive integer.
answered Sep 14, 2013 at 22:29
-
$\begingroup$ I think this post is great as teaching modular arithmetic. However, as motivation the clock is superficial and even/odd is already fully understood. I think it is much better to motivate through problems the students don't know how to solve. This is the reason modular arithmetic was created/discovered after all. $\endgroup$ Commented Sep 14, 2013 at 23:11
-
$\begingroup$ @rghthndsd: I think starting out with something that is already understood is not necessarily a bad thing. While showing students problems that are easily solved using modular arithmetic is a worthwhile thing to do, I don't think it is necessarily motivation for introducing the concept of modular arithmetic, but rather motivation for why anyone cares about it. The distinction I'm making is slight, but I think important. There is a difference between explaining why anyone would think to come up with a concept (i.e. modular arithmetic, prime, limit, manifold, etc.) [cont...] $\endgroup$ Commented Sep 14, 2013 at 23:36
-
$\begingroup$ [...cont] and explaining why that concept eventually became useful. For example, we don't talk about RSA encryption when first introducing prime numbers. Instead we have our own reasons for introducing the notion - it seems to be a natural next step in a sequence of ideas. $\endgroup$ Commented Sep 14, 2013 at 23:37
$\begingroup$
$\endgroup$
I assume you are teaching at high school level.
Well , I shall put it as a conversation :
T = Teacher, S = Student
T: "Dear students, how can you say whether a number is divisible by 9?"
S: "Given a natural number n , if the sum of digits of n is divisible by 9 , then n is divisible by 9."
T: "Do you know why it works??"
S: "..."
And then you start explaining the concept of modular arithmetic.
For more information : https://www.math.upenn.edu/~mlazar/math170/notes06-2.pdf
