Back to Basics
by t0rajir0u, Jan 17, 2007, 1:17 AM
Modular division is a topic that people don't seem to know much about, so I figured it'd be worthwhile to cover it.
Definition: We say (for integers
such that 
) that 
iff 
Definition: Given a number
, we say that 
is the multiplicative inverse of 
iff 
.
Notice that this is the same as the definition of multiplicative inverse in the real numbers, except we use equality rather than modular equivalence. Indeed, properties of multiplication and division from the real numbers are entirely preserved, which makes this a useful tool.
Problem: Calculate the last two digits of
.
I twisted around a problem I've seen several times asking for the last two digits of
. That problem is trivial if you remember that 
, but this one is less so.
Well, we're working
. That means we only have to consider 
. By Totient Theorem,
But this can only get us as far as
... Or can it? Well, let's go one
further:
Then all we have to do is figure out what the multiplicative inverse of
is. Well,
So of course
And therefore
See how nice that was?
If you're wondering how to calculate multiplicative inverses generally, it actually turns out to be equivalent to solving the linear Diophantine
Which, of course, is only possible if
(this is the condition for the existence of multiplicative inverses.) Given the set of all such 
, the product of any two of these numbers is another one 
, so we say that they form a multiplicative group (closed under multiplication, and inverses exist). This group, of course, has 
members, and it is the study of this group that is used to prove the Totient Theorem (which can be generalized to any finite group).
But I digress. Solving this linear Diophantine generally makes use of the Extended Euclidean Algorithm (which is really just an application of the division algorithm), which I may or may not get to later.
Similarly, one can define modular roots.
Definition: Given an integer, we say that is the 
root of if
For example,
because 
.
Just as there are
different roots in the complex numbers, there are (well, in prime moduli) different modular roots (in fact, those two sets of numbers have some startling similarities!). For example,
![$\sqrt[4]{ 3 }\equiv 2, 3, 10, 11 \bmod 13$](//latex.artofproblemsolving.com/7/6/5/76524d9233db7b7c83e40c884bedd9414d227226.png)
This is useful for solving polynomials, but I will leave the details to you!
Practice Problem 1: Given an odd prime
and integers 
such that 
, find integers 
such that 
.
Practice Problem 2: Factor the polynomial
. Use this factoring to prove that 
. What is 
?
Definition: We say (for integers
such that 
) that 
iff 
Definition: Given a number
, we say that 
is the multiplicative inverse of 
iff 
.Notice that this is the same as the definition of multiplicative inverse in the real numbers, except we use equality rather than modular equivalence. Indeed, properties of multiplication and division from the real numbers are entirely preserved, which makes this a useful tool.
Problem: Calculate the last two digits of
.I twisted around a problem I've seen several times asking for the last two digits of
. That problem is trivial if you remember that 
, but this one is less so.Well, we're working
. That means we only have to consider 
. By Totient Theorem,
But this can only get us as far as
... Or can it? Well, let's go one
further:
Then all we have to do is figure out what the multiplicative inverse of
is. Well,
So of course
And therefore
See how nice that was?
If you're wondering how to calculate multiplicative inverses generally, it actually turns out to be equivalent to solving the linear Diophantine
Which, of course, is only possible if
(this is the condition for the existence of multiplicative inverses.) Given the set of all such 
, the product of any two of these numbers is another one 
, so we say that they form a multiplicative group (closed under multiplication, and inverses exist). This group, of course, has 
members, and it is the study of this group that is used to prove the Totient Theorem (which can be generalized to any finite group).But I digress. Solving this linear Diophantine generally makes use of the Extended Euclidean Algorithm (which is really just an application of the division algorithm), which I may or may not get to later.
Similarly, one can define modular roots.
Definition: Given an integer
, we say that is the 
root of if
For example,
because 
.Just as there are
different roots in the complex numbers, there are (well, in prime moduli) different modular roots (in fact, those two sets of numbers have some startling similarities!). For example,![$\sqrt[4]{ 3 }\equiv 2, 3, 10, 11 \bmod 13$](http://latex.artofproblemsolving.com/7/6/5/76524d9233db7b7c83e40c884bedd9414d227226.png)
This is useful for solving polynomials
, but I will leave the details to you!Practice Problem 1: Given an odd prime
and integers 
such that 
, find integers 
such that 
.Practice Problem 2: Factor the polynomial
. Use this factoring to prove that 
. What is 
?
by FLT. Plug in zero to get 
.
.
so the multiplicative inverse exists (and is unique).
.
is undefined?
is equivalent to the degree of the polynomial that's the gcd of 
and 
.
and got to 
but i could not find a number 
am i doing somehting wrong?
,
mod 49
April 2009
March 2009