Find .
In[1]:= GCD[23456, 987654]
Out[1]= 2
Solve in integers .
In[2]:= ExtendedGCD[23456, 987654]
Out[2]= {2, {-3158, 75}}
This means that 2 is the gcd and .
Compute .
In[3]:= Mod[234*456, 789]
Out[3]= 189
Compute .
In[4]:= PowerMod[234567, 876543, 565656565]
Out[4]= 473011223
Find the multiplicative inverse of .
In[5]:= PowerMod[87878787, -1, 9191919191]
Out[5]= 7079995354
Solve .
SOLUTION
Here is one way. It corresponds to the method in Section 3.3. We calculate and then multiply it by 2389:
In[6]:= PowerMod[7654, -1, 65537]
Out[6]= 54637
In[7]:= Mod[%*2389, 65537]
Out[7]= 43626
Find with
SOLUTION
In[8]:= ChineseRemainder[{2, 5, 1}, {78, 97, 119}]
Out[8]= 647480
We can check the answer:
In[9]:= Mod[647480, {78, 97, 119}]
Out[9]= {2, 5, 1}
Factor 123450 into primes.
In[10]:= FactorInteger[123450]
Out[10]= {{2, 1}, {3, 1}, {5, 2}, {823, 1}}
This means that .
Evaluate .
In[11]:= EulerPhi[12345]
Out[11]= 6576
Find a primitive root for the prime 65537.
In[12]:= PrimitiveRoot[65537]
Out[12]= 3
Therefore, 3 is a primitive root for 65537.
Find the inverse of the matrix .
SOLUTION
First, invert the matrix without the mod:
In[13]:= Inverse[{{13, 12, 35}, {41, 53, 62}, {71, 68, 10}}]
Out[13]=
We need to clear the 34139 out of the denominator, so we evaluate 1/34139 mod 999:
In[14]:= PowerMod[34139, -1, 999]
Out[14]= 410
Since , we multiply the inverse matrix by and reduce mod 999 in order to remove the denominators without changing anything mod 999:
In[15]:= Mod[410*34139*%%, 999]
Out[15]= {{772, 472, 965}, {641, 516, 851}, {150, 133, 149}}
Therefore, the inverse matrix mod 999 is .
In many cases, it is possible to determine by inspection the common denominator that must be removed. When this is not the case, note that the determinant of the original matrix will always work as a common denominator.
Find a square root of 26951623672 mod the prime .
SOLUTION
Since , we can use the Proposition of Section 3.9:
In[16]:= PowerMod[26951623672, (98573007539 + 1)/4, 98573007539]
Out[16]= 98338017685
The other square root is minus this one:
In[17]:= Mod[-%, 98573007539]
Out[17]= 234989854
Let . Find all four solutions of .
SOLUTION
First, find a square root mod each of the two prime factors, both of which are congruent to :
In[18]:= PowerMod[19101358, (9803 + 1)/4, 9803]
Out[18]= 3998
In[19]:= PowerMod[19101358, (3491 + 1)/4, 3491]
Out[19]= 1318
Therefore, the square roots are congruent to and are congruent to . There are four ways to combine these using the Chinese remainder theorem:
In[20]:= ChineseRemainder[ {3998, 1318 }, {9803, 3491 }]
Out[20]= 43210
In[21]:= ChineseRemainder[ {-3998, 1318 }, {9803, 3491 }]
Out[21]= 8397173
In[22]:= ChineseRemainder[ {3998, -1318 }, {9803, 3491 }]
Out[22]= 25825100
In[23]:= ChineseRemainder[ {-3998, -1318}, {9803, 3491}]
Out[23]= 34179063
These are the four desired square roots.