What is the most motivating way to introduce modular arithmetic? 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?
 A: 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.  
A: 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.
A: 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
