Algebraic Structures MAPLE exercises 1

Please summarize solutions, and hand in to Pure Tutors no later than 9am on 17th March 1997. The online help will be useful; to find out about command kgb type ?kgb or use the help icon.

1. The following MAPLE program evaluates the gcd of two positive integers m and n while printing out all intermediate remainders.

   >GCD:=proc(m,n)
   >local a, j, q;
   >a[1]:=m;
   >a[2]:=n;
   >print(a[1]);
   >print(a[2]);
   >j:=1;
   >while(a[j+1]>0) do
   >q:=iquo(a[j],a[j+1]);
   >a[j+2]:=a[j]-q*a[j+1];
   >print(a[j+2]);
   >j:=j+1;
   >od;
   >a[j];
   >end;

This procedure is invoked by, for instance, GCD(1001,1997); . Use it to calculate gcd(123456789, 987654321), gcd(4259376103427393939636, 6655776103427393925657) and gcd(12360848946698171, 20000273725560978). Do a few more similar examples. Note the speed of the computation!

(The proc syntax is used to define a procedure in MAPLE. The local command designates local variables, which will not conflict with any variables of the same name used outside the procedure. The procedure is concluded with an end command. The print command prints intermediate results; it can be extended, for instance print(a,b) prints the values of a and b. There is a loop with syntax while(condition) do ⋯ od;) , which repeats while the condition is true. Finally iquo(a,b) gives the quotient of a divided by b rounded down to an integer.)

2. Modify the program in question 1 to also output r and s with gcd(m, n) = rm + sn. You will need to introduce variables r[j] and s[j], initialize them and find subsequent values in the same manner as for the a[j]s. Use your program to find values of r and s for the examples in question 1.

3. Use the program in question 2 to find the general solutions of the following congruences:

(i) 32388738474153x ≡ 49188813185538 (mod 68394898549113); (ii) 12345678987654321x ≡ 41254648430258710 (mod 55544899977733111); (iii) 83621143489848422977x ≡ 1 (mod 354224848179261915075).

If you feel ambitious write a MAPLE program to solve the general congruence: ax ≡ b (mod n).

(You may find the syntax a mod n useful. This computes the b with b ≡ a (mod n) and 0 ≤ b < n.)

4. Find the general solutions of the simultaneous congruences:

(i)  \{ \begin{matrix}x & ≡ & 8655749 & (mod 77236764) \\ x & ≡ & 73223696 & (mod 109827375) \end{matrix}

(ii)  \{ \begin{matrix}x & ≡ & 10814414562717 & (mod 11232431084437) \\ x & ≡ & 311666004239 & (mod 7238647701024) \end{matrix}

(iii)  \{ \begin{matrix}x & ≡ & 3787951605300227538 & (mod 6182136252282466497) \\ x & ≡ & 1890092147912601045 & (mod 3820773165037795910) \end{matrix}

Again, if you are feeling bold, you may like to write a MAPLE program to solve the general pair of simultaneous congruences of this form.

RJC 28/2/97