Chapter 1: Introduction to Software

The main purpose of this section is to give you a chance to practice using
Mathematica. It has several functions which are relevant to this section. 
For making computations in the integers modulo n there is a built-in function 
Mod. Thus

Mod[25 + 87,  13]

and

Mod[21*86,  17]

and

Mod[2^12,  7]

A more efficient way of computing powers  mod n is to use the function PowerMod:

PowerMod[2,  12,  7]

For any real number a the function  N[a, m]will compute a to m digits. For example,

N[1/7,  20]

So we see that the period of 1/7 is 1,4,2,8,5,7,  as discussed above. Similarly

N[1/19,  40]

Thus the period of  1/19 is  0,5,2,6,3,1,5,7,8,9,4,7,3,6,8,4,2,1 , which has length 18 . And

Mod[10^18  -  1,  19]

but for smaller k,  (10^k) - 1 ≢ 0 mod 19. We can do these calculations for all the primes less than 30 say, 
and tabulate the results. They confirm Theorem 1.3.

TableForm[{{"prime", 3, 7, 11, 13, 17, 19, 23, 
          29}, 
{"period", 2, 6, 2, 6, 16, 18, 22, 
          28}, 
{"k", 2, 6, 2, 6, 16, 18, 22, 
          28}}]

Interestingly

1001 = (10^3) + 1 = 7·11·13 ,

so that

(10^3) + 1 ≡ 0  mod 7 .

Similarly,

Mod[10^9  +  1,  19]

What do you think is going on? Experiment a bit and try to make a conjecture.

Given a pair of relatively prime integers a  and b , the function ExtendedGCD will compute integers s  and t  so that  1 = as + bt . For example,

ExtendedGCD[57,  21]

This means that   3 = 3·57 - 8·21 . If we want to find the multiplicative
inverse of 105 in  (Subscript[𝔽, 197]), we can enter

ExtendedGCD[105,  197]

So  1  =  -15 · 105 + 8 · 197 , and  -15 = 182  is the multiplicative inverse of 105 .

	In the package NumberTheory`NumberTheoryFunctions` there is a function called ChineseRemainderTheorem  which will solve two such congruences simultaneously - in fact it will solve a system:

x ≡ (Subscript[b, 1]) (mod (Subscript[n, 1]))

⋮

x ≡ (Subscript[b, r]) (mod (Subscript[n, r]))

To use it you first load the package:

<< NumberTheory`NumberTheoryFunctions`

Then you simply enter

		ChineseRemainderTheorem[{(Subscript[b, 1]), ⋯, (Subscript[b, r])}, {(Subscript[n, 1]), ⋯, (Subscript[n, r])}]

So in our example:

ChineseRemainderTheorem[{14,  6},  {24,  31}]