Modular arithmetic began as a different way of thinking about the integers.
In ordinary arithmetic, the integers are arranged on the real number line.
With modular arithmetic, however, the integers are arranged on a circle.
The modulus tells you how many equally spaced marks you have on the circle.
For example, if you're working "mod 7"
then there will be 7 marks, labelled from 0 to 6.
As you count up,
you move along the circle from one mark to the next
in a clockwise direction...
And as you count down, you simply travel counterclockwise...
You can freely add, subtract, and multiply the numbers on this circle.
For example, 4 + 5 would be ...
2.
And 3 - 4 would be ...
6.
So you can think of modular arithmetic as "circular arithmetic".
Every integer corresponds to a number on this circle.
To find which number, divide the integer by 7,
and the remainder is the corresponding number.
So the number 0 mod 7 corresponds to every multiple of 7.
1 mod 7 corresponds to every integer with a remainder of 1 when you divide by 7.
And so on...
One of the essential properties of modular arithmetic
is if you pick ANY integer from one class
and add, subtract, or multiply it with any integer from a second class,
the result will always be in the same, third class.
For example,
any integer with a remainder of 2
multiplied by any integer with a remainder of 3
will always give you an integer with a remainder of 6.
In most programming languages,
you use the % operator for the modulus operator.
19 mod 5 is 4 because when you divide 19 by 5 the remainder is 4.
In Mathematica and the Wolfram Language, you use the Mod function.
The first argument is the number,
and the second argument is the modulus.
You can compute the mod of a negative integer.
If you're not familiar with computing the remainder when you divide a negative integer by a positive integer,
you can also think of this as the first non-negative integer you get if you keep adding 5 to -19.
Going further,
you can compute the mod of any real number.
The result just shifts the real number by multiples of the modulus
until you get a number in the range [0,5), excluding 5.
The definitions of a quotient and remainder can be generalized to all complex numbers.
The Mod function supports these computations, too.
Exponentiation in modular arithmetic can be very fast --
provided you approach it correctly.
From Elementary Number Theory, there are a few key results that provide shortcuts for modular exponentiation.
Fermat's Little Theorem says that for any number a not congruent to 0, "a to the p -1 is congruent to 1 mod p".
This result is limited since it only works with a prime modulus.
Euler later generalized this to any modulus with his totient function,
also called the φ function.
The way these theorems help is that if you have a^b,
then you can divide the exponent by φ(n)
and reduce this to a^r mod n.
Since the remainder is always less than n,
you now have a much simpler computation.
Let's see how using the right function can make a difference.
Suppose you want Mathematica to perform this computation.
Here, Mathematica will first compute 143 to this massive power,
then find the remainder when you divide by 17.
This takes a moment to do.
We can find out how long by using the Timing function.
For a faster result, use the PowerMod function.
With this function, you pass in the base, exponent, and modulus.
The value is returned much more quickly.
If we time the PowerMod function,
we see the computation is performed with almost no delay.
PowerMod can also be used to find modular inverses --
if they exist.
For example, to find the multiplicative inverse of 5 mod 101,
you call the PowerMod function with an exponent of -1.
We can verify that 81 is the inverse by computing 5 times 81 mod 101.
This is indeed the inverse.
For a prime modulus, every non-zero integer has an inverse.
This is not the case with a composite modulus.
For example, does 7 have an inverse mod 20?
It does: 3.
But what about 6?
No, it doesn't have an inverse since it's not relatively prime to 20.
Mathematica also has a ModularInverse function
for those times when you simply can't be bothered to type in 3 arguments to the PowerMod function.
Just enter the number and the modulus, and if an inverse exists, you'll get it.
PowerMod can also find roots mod n.
For example, to find the square root of 3 mod 71,
just raise 3 to the 1/2 power.
We can verify that this is a square root of 3 by computing 28^2 mod 71.
And you can compute other roots, too.
Here is how you compute the 5th root of 20 mod 71.
But not every integer mod 71 has a fifth root.
The Solve function in Mathematica can also be used to solve modular equations.
To do this, just type in the Solve command as you normally would.
Then, specify the modulus using the Modulus option.
Keep in mind the Solve function is only looking for solutions amongst the integers mod 41.
It is not computing the solutions in algebraic extensions.
So some quadratic equations may not have a solution in the finite field of order 41.
This doesn't mean solutions do not exist.
You'll just need to move up to a suitable extension field to find them.
The Solve function can also be used to solve systems of equations over the complex numbers.
You can also use this function to solve systems of modular equations.
All you need to do is specify the Modulus.
There are many other functions for modular arithmetic.
For example:
the PolynomialMod function will reduce the coefficients of a polynomial to your specified modulus.
To find a primitive root for a specific modulus, use the PrimitiveRoot function.
And if you need a list of all primitive roots, use the PrimitiveRootList function.
When working mod n you'll also make frequent use of Euler's totient function.
This is built into Mathematica and is called EulerPhi.
You can even compute the order of an element mod n with the MultiplicativeOrder function.
These functions will get you well on your way to using Mathematica for modular arithmetic.
Did you know we're building a course on the essentials of Mathematica & and the Wolfram Language?
Interested?
Then sign up to our Mathematica mailing list so you'll know when it launches!
Not interested?
Then don't sign up to our Mathematica mailing list so you won't know when it launches.