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

>> gcd(23456,987654)

ans =
   2

If larger integers are used, they should be expressed in symbolic mode; otherwise, only the first 16 digits of the entries are used accurately. The present calculation could have been done as

>> gcd(sym(’23456’),sym(’987654’))

ans =
   2

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

>> [a,b,c]=gcd(23456,987654)

a =
   2

b =
   -3158

c =
   75

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

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

>> mod(234*456,789)

ans =
   189

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

>> powermod(sym(’234567’),sym(’876543’),sym(’565656565’))

ans =
   5334

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

>> invmodn(sym(’87878787’),sym(’9191919191’))

ans =
   7079995354

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

SOLUTION

To solve this problem, we follow the method described in Section 3.3. We calculate ${7654}^{-1}$ and then multiply it by 2389:

>> invmodn(7654,65537)

ans =
   54637

>> mod(ans*2389,65537)

ans =
   43626

Find $x$ with

SOLUTION

To solve the problem we use the function crt.

>> crt([2 5 1],[78 97 119])

ans =
   647480

We can check the answer:

>> mod(647480,[78 97 119])

ans =
    2   5   1

Factor 123450 into primes.

>> factor(123450)

ans =
    2    3   5   5   823

This means that $123450=2^1{3}^1{5}^2{823}^1$.

Evaluate $\varphi (12345)$.

>> eulerphi(12345)

ans =
   6576

Find a primitive root for the prime 65537.

>> primitiveroot(65537)

ans =
   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)(\mathrm{m}\mathrm{o}\mathrm{d}999)$.

SOLUTION

First, we enter the matrix as $M$.

>> M=[13 12 35; 41 53 62; 71 68 10]; 

Next, invert the matrix without the mod:

>> Minv=inv(M)

Minv =
     233/2158     -539/8142    103/3165
     -270/2309    139/2015     -40/2171
     209/7318     32/34139    -197/34139

We need to multiply by the determinant of $M$ in order to clear the fractions out of the numbers in $Minv$. Then we need to multiply by the inverse of the determinant mod 999.

>> Mdet=det(M)

Mdet =
   -34139

>> invmodn(Mdet,999)

ans =
   589

The answer is given by

>> mod(Minv*589*Mdet,999)

ans =
    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:

>> powermod(sym(’26951623672’),(sym(’98573007539’)+1)/4,sym(’98573007539’))

ans =
   98338017685

The other square root is minus this one:

>> mod(-ans,32579)

ans =
   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)$:

>> powermod(19101358,(9803+1)/4,9803)

ans =
   3998
>> powermod(19101358,(3491+1)/4,3491)

ans =
   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:

>> crt([3998 1318],[9803 3491])

ans =
   43210

>> crt([-3998 1318],[9803 3491])

ans =
   8397173

>> crt([3998 -1318],[9803 3491])

ans =
   25825100

>> crt([-3998 -1318],[9803 3491])

ans =
   34179063

These are the four desired square roots.