/sci/ - Science & Math

The integers are a complicated structure. No matter how many integers you've counted, there will always be more. They are unending. Sometimes you have propositions that are supposed to hold for all integers and it's unclear how you would prove it without checking it for every single integer. Modular arithmetic helps with that. It massively reduces the amount of information and simplifies things. You will no longer have an infinite number of things, there are only finitely many classes mod n.
Let's say that you want to prove that given distinct list of 101 integers, two of them differ by a multiple of 100. At first it might sound like a complicated proposition. How would you prove that for any collection of integers? There are infinitely many such options, how do you even start? But then you notice you can work mod 100, where there are only 100 options. And two of the integers must correspond to the same option, which means exactly that their difference is a multiple of 100, so the problem is solved.
Another good example is considering integral solutions to polynomials. For example, how do you show that no integer x satisfies x^42 - 12x^40 + 4 =0? The task might seem daunting at first, but then you might try reducing the equation modulo 3. All you need is to check 3 cases: 0,1,2. If none of them are a solution, that means there's no integral solution. And indeed, it's easy to check that none of these work, so we have our proof.
Modular arithmetic is of course also useful for encryption. The ring Z/nZ is finite so operations that would be completely intractable in the integers like raising a number to a 2000 power become very feasible and this opens up many possibilities.
Taking note of facts about modular arithmetic also makes checking divisibility much easier. For example, to check that a number d_n d_(n-1) ... d_1 in base 10 is divisible by 11 just notice that 10=-1 mod 11 and so 10^n = (-1)^n which is very easy to calculate (-1 if n is odd and 1 if n is even).

>tfw my posts are now in the 4chan annals.