Find $gcd(23456\text{,}987654)$.

In[1]:= GCD[23456, 987654]

Out[1]= 2

Solve $23456x+987654y=2$ in integers $x\text{,}y$.

In[2]:= ExtendedGCD[23456, 987654]

Out[2]= {2, {-3158, 75}}

This means that 2 is the gcd and $23456\cdot (-3158)+987654\cdot 75=2$.

Compute $234\cdot 456(\text{mod}789)$.

In[3]:= Mod[234*456, 789]

Out[3]= 189

Compute ${234567}^{876543}(\text{mod}565656565)$.

In[4]:= PowerMod[234567, 876543, 565656565]

Out[4]= 473011223

Find the multiplicative inverse of $87878787(\text{mod}9191919191)$.

In[5]:= PowerMod[87878787, -1, 9191919191]

Out[5]= 7079995354

Solve $7654x\equiv 2389(\text{mod}65537)$.

SOLUTION

Here is one way. It corresponds to the method in Section 3.3. We calculate ${7654}^{-1}$ and then multiply it by 2389:

In[6]:= PowerMod[7654, -1, 65537]

Out[6]= 54637

In[7]:= Mod[%*2389, 65537]

Out[7]= 43626

Find $x$ 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 $123450=2^1{3}^1{5}^2{823}^1$.

Evaluate $\varphi (12345)$.

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 $\left(\begin{array}{ccc}13& 12& 35\\ 41& 53& 62\\ 71& 68& 10\end{array}\right)(\text{mod}999)$.

SOLUTION

First, invert the matrix without the mod:

In[13]:= Inverse[{{13, 12, 35}, {41, 53, 62}, {71, 68, 10}}]

Out[13]= $\left\{\right\{{\displaystyle \frac{3686}{34139}}\text{,}-{\displaystyle \frac{2260}{34139}}\text{,}{\displaystyle \frac{1111}{34139}}\left\}\text{,}\right\{-{\displaystyle \frac{3992}{34139}}\text{,}{\displaystyle \frac{2355}{34139}}\text{,}-{\displaystyle \frac{629}{34139}}\}\text{,}\{{\displaystyle \frac{975}{34139}}\text{,}{\displaystyle \frac{32}{34139}}\text{,}-{\displaystyle \frac{197}{34139}}\}\}$

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 $410\cdot 34139\equiv 1(\text{mod}999)$, we multiply the inverse matrix by $410\cdot 34139$ 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 $\left(\begin{array}{ccc}772& 472& 965\\ 641& 516& 851\\ 150& 133& 149\end{array}\right)$.

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 $p=98573007539$.

SOLUTION

Since $p\equiv 3(\text{mod}4)$, 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 $n=34222273=9803\cdot 3491$. Find all four solutions of $x^2\equiv 19101358(\text{mod}34222273)$.

SOLUTION

First, find a square root mod each of the two prime factors, both of which are congruent to $3(\text{mod}4)$:

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 $\pm 3998(\text{mod}9803)$ and are congruent to $\pm 1318(\text{mod}3491)$. 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.