Answers to Selected Tutorial Problems

Tutorial 2, Q4

Define operators in vector calculus: divergence ∇ · A, curl ∇ × A, gradient ∇f, and Laplacian (∇^2) f.  We  can use the following definitions which work in any dimensions except ∇ × A, which is specific to three dimensions.  Note that ∇ = (∑_(i = 1)^d)(Subscript[e, i])(∂_i), where (Subscript[e, i]) is unit vector in i-th direction.  Also, (∇^2) 
          f = ∇· (∇f).

Div[v_, 
          arg_] := Inner[D, v, arg, Plus];

    Curl[{v1_, v2_, v3_}, {x_, y_, z_}] :=  {D[v3, y] - D[v2, z],  
          D[v1, z] - D[v3, x], D[v2, x] - D[v1, y]};

    Grad[f_, arg_] := D[f, #] & /@ arg ; 

    Laplacian[f_, arg_] := Div[Grad[f, arg], arg]

Tutorial 3, Q2 & 3

The function func[ ] selects the entries in a list that are positive numbers.  The order of the elements are preserved.   It does this by moving the members of the first list to second list one by one in ff[ ].   Note that definitions will be applied recursively until none of the rules can be applied.

func[l_] := ff[l, {}];
ff[{}, r_] := r;
ff[{h_, t___}, {r___}] := ff[{t}, {r, h}] /; h > 0;
ff[{h_, t___}, {r___}] := 
      ff[{t}, {r}] /; (h ≤ 0 || 
            Head[h] == Symbol)

func[{1, 2, a, -3, 7}]

The following program counts the repeated consecutive elements, producing a list of pairs of {element, count}.

runEncode[lst_List] := 
      Map[{#, 1} &, 
          lst] //. {u___, {v_, r_}, {v_, s_}, w___} -> {u, {v, r + s}, 
            w}

runEncode[{a, a, b, 1, 2, 2, 2, d}]

Tutorial 3, Q4

The best way to read/write data that are in regular array or matrix form appears to be the command Import[ ] and Export[ ].

?Export

Tutorial 4, Q2

Quaternions are expressions of the form
	a 1 + b i+c j + d k
where (i^2)=(j^2)=(k^2)=-1.  In addition, the product of i,j,kbehaves like cross product of unit vector in three dimensions, such as i j = -j i= k.  The question is the algebraic domain of the quaternions.

It is clear that it is a ring: addition is a group, with 0= 0 1+0 i+0 j+0 k the additive identity.  Multiplication is distributive over addition.  The multiplicative identity is 1.  Most importantly, multiplication is associative.   To show this we just need to show that the basis are associative: e.g.,
	(i j) k = k k = -1, i (j k) = i i = -1, so  (i j) k = i (j k) also
	(i i) k = - k,  i (i k) = i (-j) = -(i j) = -k, so  (i i) k = i (i k), and 
	(i j) i =  k i =j,  i (j i) = i (-k) = -(i k) = j, so  (i j) i = i (j i), and 
	(i i) i = - i,  i (i i) = i (-1)  = -i, so  (i i) i = i (i i), and so on.  I believe all the 3×3×3=27 cases can be verified.

It is not a field since elements don't commute.  However, each nonzero element has an inverse.  Let us give an explicit formula for inverse.   Consider
(a 1 + b i+c j + d k)(a 1 - b i-c j -d k)=(a^2)+(b^2)+(c^2)+(d^2) = (R^2).
The cross terms vanish due to, e.g., i j + j i = 0.   Divide (R^2) to both sides of the above equation, as long as R is not zero, we find:
(((a 1 + b i+c j + d k))^(-1))=(a 1 - b i-c j -d k)/((a^2)+(b^2)+(c^2)+(d^2)).

Another representation of the quaternions is to identify the basis with the matrices (related to Pauli matrices):
	1=(({{1, 0}, {0, 0}})),  i=(({{i, 0}, {0, i}})),  j=(({{0, 1}, {-1, 0}})),  k=(({{0, i}, {i, 0}})),     i = (Sqrt[-1])
Then the addition and multiplication correspond to matrix addition and multiplication.

Tutorial 4, Q3.

This question discusses the relationship between polynomials modulo (1 + (x^2)) and complex number (a + b i).  Such polynomials are always of the form
	a  +  b x,   a,  b  ∈  R
Addition forms an Abelian group with 0 as additive identity.  Multiplication identity is 1.  Each nonzero element has an inverse:  The argument is similar to Q2.  Since we have
	(a + b x) ( 
            a  -  b x) mod (1 + (x^2))  =  
        (a^2) - (b^2) (x^2) mod (1 + (x^2))
= (a^2) + (b^2)
Thus (((a + b x))^(-1)) mod (1 + 
              (x^2))  =  (a - b x)/((a^2) + (b^2)) mod (1 + 
              (x^2)).   We have used the fact that (x^2) mod (1 + (x^2))  =  -1.   Association and distribution are automatic for polynomials.  So it forms a field.

We can identify a linear polynomial a + b x with a vector (a, b).  The set of these vectors form a linear vector space.  In a linear vector space, we can add
 (a, b) + (c, d) = (a + c, b + d).  
 We can multiply vector with a number
 λ (a,  
          b)  =  (λ a,  λb).  
 Zero vector is (0,0), and two basis vectors of the space can be choosing to be (1,0) and (0,1).  At most two vectors are linearly independent.  Any vector can be expressioned as a linear combination of the basis.  The space is two dimensional.

We see that the rules for addition and multiplication for the polynomials mod (1 + (x^2)) is exactly the same as that for complex numbers:
(a + b x)  +  (c  +  d x)  =  (a + 
              c)  +  (b + d) 
            x , 
(a + b x) *(c + 
              d x)   =  (a c  -  
              b d)  +  (b c + a d) x       [
                mod (1 + (x^2))].
For complex number, we have
\(TraditionalForm\`\((a + b\ i)\)\  + \ \((c\  + \ d\ i)\)\  = \ \((a + 
              c)\)\  + \ \((b + d)\) 
            i\ , 
\((a + b\ i)\)\ *\((c + d\ i)\)\ \  = \ \((a\ c\  - \ 
              b\ d)\)\  + \ \((b\ c + 
                a\ d)\)\ i\ , \ \ \ i\  = \ \(\(\@\(-1\)\)\(.\)\)\)
Where a, b, c, d ∈ R.  Thus the mapping from polynomial (a + b x) to the set of complex number (a + i b), identifying the real part of the complex number with the constant term a and imaginary part with b the coefficient of x, is a one-to-one and onto mapping.  Thus the field of polynomials mod (1 + (x^(2 ))) and the complex number C are isomorphic to each other.

Tutorial 5, Q2

Consider Gaussian integers of the form
	G: a + b i,  a,  b  ∈  Z,  i = (Sqrt[-1]).
We want to show that it is an Euclidean domain.

(a) To show that Gaussian integers form a ring, we note that addition is closed and is an Abelian group, with 0 as additive identity.  Multiplication is associative (since this is so for complex numbers).  The multiplicative identity is 1.  Multiplication is distributive over addition.

Cancellation law is valid for complex numbers, so it is also valid for Gaussian integers. Thus the set of Gaussian integers form an integral domain.

We now need to see how to do division with Gaussian integers, such that
	\(TraditionalForm\`a = 
        b\ q\  + \ 
          r, \ \ \ \ \ \(\(|\)\(r\)\(|\)\(\ \)\(\(<\)\(\ \)\(\(|\)\(b\)\(|\)\)\)\), \ \ \ \ a, \ b, \ 
      q, \ \(\(r\)\(\ \)\(∈\)\(\ \)\)\)G.
We try to find the answer in C.  Let denote a (b^(-1)) = c  +  
            i d  ∈C, where c and d are real numbers. We separate out a nearest integer part and a fractional part for c and d:
	\(TraditionalForm\`c\  = \ 
        c\_I + c', \ \ \ \(\(|\)\(c'\)\(|\)\(\ \)\(\(≤\)\(\ \)\(1/
            2\)\)\), 
d = \ 
        c\_I + d', \ \ \ \ \ \(\(|\)\(d'\)\(|\)\(\ \)\(\(≤\)\(\ \)\(1/2\)\)\), \)
where (Subscript[c, I]), (Subscript[d, I]) ∈ Z.  This is possible as a given real number is at most  1/2 away from the nearest integer.  Let the quotient q =  (Subscript[c, I]) + i (Subscript[d, I]), then a - b q  =  r must be in G.  This is obvious since a, b and q are in G, and G is a ring.   We only need to show \(TraditionalForm\`\(\(\(|\)\(r\)\(|\)\(\ \)\(\(<\)\(\ \)\(\(|\)\(b\)\(|\)\)\)\)\(:\)\)\)  
	\(TraditionalForm\`\(\(|\)\(r\)\(|\)\)\  = \ \(\(\(|\)\(a - 
              b\ q\)\(|\)\) = \(\(\(|\)\(b(c + \ i\ d)\  - \ 
                b\ q\)\(|\)\)\  = \ \(\(\(|\)\(b || 
                  c' + i\ d'\)\(|\)\(
\)\(\(≤\)\(\ \)\(\(|\)\(b\)\(|\)\(\ \)\(\@\(\((1/2)\)\^2 + \((1/2)\)\^\(\(2\)\(\ \)\)\)\)\)\)\) = \(\(|\)\(b\)\(|\)\(\(\(/\)\(\@2\)\)\(<\)\)\(|\)\(b\)\(|\)\(.\)\)\)\)\)\)

(b) Units are the numbers that have inverses.  Clearly
	1*1 = 1, (-1)*(-1)  =  
        1,    i*(-i)  = 1.
The units u in G are 1, -1,  i,  and  - i. Examples of primes are 2, 3, 5, 7, ..., 1 + i, 1 - i,  3 + 5 i.  a and b are associates of each other if a | b and b | a.   Then a and b must be related by  a unit u, i.e., a = u b.   For examples, 3 and -3 are associates, so is 3 and 3 i.

Tutorial 5, Q3.

Let work out the steps of extended Euclidean algorithm.  The division algorithm gives the recursive relation for remainder sequence:
	(Subscript[r, n])  -  (Subscript[r, n + 1]) (Subscript[q, n]) = 
        (Subscript[r, n + 2]);      (Subscript[r, 0]) = a,  (Subscript[r, 1]) = b,  n = 0,  1,  
      2,   ... 
(Subscript[q, n]) is the quotient of (Subscript[r, n]) divided by (Subscript[r, n + 1]).  We stop when the remainder becomes zero; the last nonzero remainder is the GCD.  Similarly
	(Subscript[s, n])  -  (Subscript[s, n + 1]) (Subscript[q, n]) = 
        (Subscript[s, n + 2]);      (Subscript[s, 0]) = 1,  (Subscript[s, 1]) = 0,  n = 0,  1,  
      2,   ... 
(Subscript[t, n])  -  (Subscript[t, n + 1])  (Subscript[q, n]) = 
        (Subscript[t, n + 2]);        (Subscript[t, 0]) = 0,  (Subscript[t, 1]) = 1,  n = 0,  1,  
      2,   ... 
such that 
	(Subscript[r, n]) = a (Subscript[s, n]) + b (Subscript[t, n])    for n  = 0,  1,  2,   ... 
We used a notation that is different from Algorithm 2.1 which makes thing clearer.  The important quantity to compute is (Subscript[q, n]).

We start with (Subscript[r, 0]) = a(x)  = 
          4  (x^4) + 13  (x^3) + 15  (x^2) + 7  x + 1, (Subscript[r, 1]) = b(x)  = 2  (x^3) + (x^2) - 4  x - 3, (Subscript[s, 0]) = 1,  (Subscript[s, 1]) = 0,  (Subscript[t, 0]) = 0,  (Subscript[t, 1]) = 1,  and compute (Subscript[q, 0]).
                              
	\(TraditionalForm\`\(\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \)\(2  
          x\ \ \ \  + \ 11\/2

      2  x\^3\  + \ x\^2\  - \ 4  x\  - \ 
        3\ \@\(\(4  x\^4\)\(\ \)\(+\)\(\ \)\(13  x\^3\)\(\ \)\(+\)\(\ \)\(15  x\^\(\(2\)\(\ \)\)\)\(+\)\(\ \)\(7  x\)\(\ \ \)\(+\)\(\ \ \)\(1\)\(\ \ \)\)

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 4  x\^4\  + \ \ \ \ 2 
           x\^3\ \ \  - \ 8  x\^2\ \  - \ 6\ x

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ─\ \ \ \(\(\(\(\(\(\(\(\(─--\)--\)--\)--\)--\)--\)--\)--\)--\) - 
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 11\ x\^\(\(3\)\(\ \)\)\ \ \  + 23\ x\^2\  + 13\ x\ \ \  + 1\ 

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 11\ x\^3 + \ \(11\/2\) x\^2\  - 22  x\  - 33\/2

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \(--\(--\(--\(--\(--\(--\(--\(--\(--
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \(35\/2\)\)\)\)\)\)\)\)\)\) 
          x\^2 + 35  x + 35\/2\)\)\)

Thus, (Subscript[q, 0]) = 2  x + (11/2), (Subscript[r, 2]) = (35/2) ((x^2) + 2  x + 1), (Subscript[s, 2]) = (Subscript[s, 0]) - (Subscript[s, 1]) (Subscript[q, 0]) = 1, (Subscript[t, 2]) =  (Subscript[t, 0]) - (Subscript[t, 1]) 
              (Subscript[q, 0]) =  -(Subscript[q, 0]) = -2 x  - (11/2).  We now do the second division:

\(TraditionalForm\`\(\(	\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \)\(\(4\/35\) x\  - 6\/35

      \(35\/2\) x\^2\  + \ 35  x\  + \ 
        35\/2\ \@\(\(\ \)\(\(2  x\^3\)\(\ \)\(+\)\(\ \ \ \)\(x\^2\)\(\ \)\(-\)\(\ \)\(4 \( x\^\ \)\)\(-\)\(3\)\(\ \ \)\)\)

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 2  x\^3\  + \ 4  x\^2\  + 
        2\ x\ 

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ─\ \ \ \(\(\(\(\(\(─--\)--\)--\)--\)--\)--\)

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \(-3\) 
          x\^\(\(2\)\(\ \)\)\  - 6\ x\  - 3\ 

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \(-3\) 
          x\^2\  - 6  x\  - 3

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \(--\(--\(--\(--\(\(--
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0\)\(\ \ \)\)\)\)\)\)\)\)\)

Thus, (Subscript[q, 1]) = (4/35) x - (6/35), (Subscript[r, 3]) = 0, (Subscript[s, 3]) = (Subscript[s, 1]) - (Subscript[s, 2]) (Subscript[q, 1]) = 0 - 
              1*(Subscript[q, 1]) = -(4/35) x + (6/35),  (Subscript[t, 3]) = (Subscript[t, 1]) - (Subscript[t, 2]) (Subscript[q, 1]) =  
          1  - (-2 x - (11/2))*((4/35) x - (6/35)).

GCD(a(x), b(x))=(35/2) (x^2) + 35  x + (35/2),  s(x) = (Subscript[s, 2]) = 1, t(x) = (Subscript[t, 2]) = -2 x - (11/2).   s(x) and t(x) is such that we have GCD(a(x), 
          b(x)) = s(x) a(x) + t(x) b(x).  We can verify:

a = 
        4  x^4 + 13  x^3 + 15  x^2 + 7  x + 1;
b = 2  x^3 + x^2 - 4  x - 3;
s = 1;
t = -2 x - 11/2;
gcd = 35/2  x^2 + 35  x + 35/2;
Simplify[gcd  -  a*s - b*t]

Tutorial 5, Q1

Given the following equations:
	2  x +  4  y - 2  z = 
        1, 
2  x +      y  +    z = 
        3, 
5  x  - 3  y + 7  z = 0, 
We solve it first in Z\(TraditionalForm\`\_3\), Z\(TraditionalForm\`\_5\), Z\(TraditionalForm\`\_7\), Z\(TraditionalForm\`\_11\).   We can use either the positive representation (numbers range from 0 to p - 1),  or symmetric representation ( numbers from -(p - 1)/2 to (p - 1)/2).   I'll use positive presentation in solving the equations.

Z\(TraditionalForm\`\_3\):
	2  x + y + z = 1, 
2  x + y + z = 
        0, 
2  x   +  z  =  0. 
The system is inconsistent, as the first two equations has the same coefficients but different right-hand side.  There is no solution.   In any case the determinant d  ≡ 0  (mod 3).

Z\(TraditionalForm\`\_\(\(5\)\(:\)\)\)
	2  x + 4  y + 3  z = 1,          (1)
2  x + y + z  =  
        3,                (2)
0 x  + 2  y + 2  z  = 
        0.          (3)
To be able to preserve the value of determinant we use only steps that don't multiply a number to an equation.  First, we replace (2) by  (2)-(1), get
	[2	4	3	1]
	[0	2	3	2]	(because 1 - 4 ≡ -3 ≡ 
        2 mod 5)
	[0	2	2	0]	
Now we do (3)-(2), we get
	[2	4	3	1]
	[0	2	3	2]
	[	0	4	3]	(because 2 - 3 ≡ -1 ≡ 
        4 mod 5)
so the determinant is obtained from the product of the diagonal elements d  ≡ 2*2*4 ≡ 16 ≡ 
        1 mod  5.  Using the backward substitution step, we get 
	 z ≡ ((4^(-1))*3)  ≡  
        4*3 ≡ 12 ≡ 
        2 mod 5, 
y ≡ 
        (2^(-1))*(2 - 3  z) ≡ 
        3*(2 - 3*2) ≡ -12 ≡ 
        3  mod 5, 
x ≡ 
          (2^(-1))*(1 - 3  z - 4  y)  =  4 mod 5. 
The values for (Subscript[d, x]) = x d  ≡  4,  
      (Subscript[d, y]) = y d ≡ 3,  (Subscript[d, z]) = z d ≡ 2,  all mod 5.

The steps for Z\(TraditionalForm\`\_7\)and Z\(TraditionalForm\`\_11\) are similar.  We find the following results (ignore the case of p = 3):
\(TraditionalForm\`p\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ d\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ d\_x\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ d\_y\ \ \ \ \ \ \ \ \ \ \ \ \ d\_z\)
\(TraditionalForm\`5\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 4\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 3\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 2\)
\(TraditionalForm\`7\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 6\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 4\)
\(TraditionalForm\`11\ \ \ \ \ \ \ \ \ \ \ \ \ \ 6\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 10\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 8\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 1\)

Using the Chinese remainder theorem, we reconstruct solutions in Z for the 4 quantities d,  (Subscript[d, x]),  (Subscript[d, y]),  (Subscript[d, z]).   For example, using the mix-radix expansion, let
d  =  (Subscript[v, 0]) + (Subscript[v, 1]) 5 + (Subscript[v, 2]) 5*7.
In mod 5,  we get  d mod 5  =  1  =  (Subscript[v, 0]).   In mod 7, we have d mod 7  =  (Subscript[v, 0]) + (Subscript[v, 1]) 5  =  1 + 
              5  (Subscript[v, 1]) =  6.   So (Subscript[v, 1]) =  (5^(-1)) (6 - 1) = 3*5 = 
            1 mod 7.  Inverse of 5 in mod 7 is 3, since  3*5= 15 ≡ 1 mod 7.   In mod 11, we get 6 = 1 + 1*5 + (Subscript[v, 2])*5*7, or  0 = (Subscript[v, 2]) 5*7, so (Subscript[v, 2]) = 0.    Thus d ≡  6 mod (5*7*11)  =  
        6 mod  385.

Similarly for (Subscript[d, x]), we get  (Subscript[v, 0]) =  4.  In mod 7, we get  0 = 4 + (Subscript[v, 1]) 5, so \(TraditionalForm\`v\_1 = \(\(5\^\(-1\)\) \((\(-4\))\) = \(3*\((\(-4\))\) ≡ \(-12\) = 2\ mod\ 7. \)\)\)   In mod 11, we have 10 = 4 + 2*5 + (Subscript[v, 2])*35,  or \(TraditionalForm\`v\_2 = \ \(\((35)\)\^\(-1\)\) \((\(-4\))\) ≡ \(2\^\(-1\)\) \((\(-4\))\) ≡ 
          6*\((\(-4\))\) ≡ 9\ mod\ 11\).   Thus (Subscript[d, x]) = 4 + 2*5 + 9*5*7 = 
          329 ≡ -56 mod 385.   The second number is in symmetric representation.  To be able to handle negative solutions in equations, the final answers have to be in the symmetrical representation.   Go through the steps for (Subscript[d, y])and (Subscript[d, z]), we find:
	d = 6,    (Subscript[d, x]) = -56,    (Subscript[d, y]) = 
        63,    (Subscript[d, z]) = 67     (mod 385).
Thus the solution for x, y, z in Q is (due to Cramer's rule)
	\(TraditionalForm\`x = \(d\_x/
            d = \(\(-\(56\/6\)\) = \(-\(28\/3\)\)\)\), 
y = \(d\_y/d = \(63\/6 = 21\/2\)\), 
z = \(d\_z/
            d = \(\(67\/6\)\(.\)\)\)\)

Tutorial 6.  Q3.

We compute the square-free factorization of the polynomial with coefficient in Z\(TraditionalForm\`\_2\)
	b(x)=(x^10) + (x^6) + (x^5) + (x^3) + (x^2) + 1      ∈  (Subscript[Z, 2])[x].

The steps for square-free factorization are:
	Let a =  (Subscript[a, 1]) ((Subscript[a, 2])^2) ((Subscript[a, 3])^3) ...  
          ((Subscript[a, k])^k) ((Subscript[a, j])are square-free factor),
	(1)  compute c = GCD(a, a') = (Subscript[a, 2]) ((Subscript[a, 3])^2) ...  
              ((Subscript[a, k])^(k - 1));
	(2)  compute factor of a,  w = a/c = (Subscript[a, 1]) (Subscript[a, 2]) (Subscript[a, 3]) ...  
            (Subscript[a, k]);
	(3)  compute another GCD,  y = GCD(w, c) = (Subscript[a, 2]) (Subscript[a, 3]) ...  (Subscript[a, k]);
	(4)  the first factor is given by z = w/y = (Subscript[a, 1]);
	(5)  Let a  ←  c, repeat step (1) to (4),  last step is then GCD(a, a') = unit.
	(6) If a' = 0, do a ← (a^(1/p)) and factor a.

First iteration: 
a = a(x),  
      a' = b' (x) = 
          10  (x^9) + 6  (x^5) + 5  (x^4) + 3  (x^2) + 2  x ≡  
            (x^4) + (x^2)   mod 2.
c = GCD(a, 
            a') = GCD((x^10) + (x^6) + (x^5) + (x^3) + (x^2) + 1, 
              (x^4) + (x^2)).
To compute the above GCD, we do long division mod 2.
\(TraditionalForm\`\(\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \)\(x\^6\ \  + x\^4\  + x

      x\^4 + 
        x\^2\ \ \ \@\(x\^10\ \ \ \ \ \  + \ \ \ \ \ \ \ x\^6 + x\^5 + x\^3 + x\^2 + 1\)

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^10 + 
        x\^8

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ___  ___  ___  ___  ___  ___  ___  ___  __

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^8\ \ \  + \ x\^6\  + x\^5 + x\^3 + x\^2 + 1

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^8\ \ \  + \ x\^6

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ __\ \ \ \ ___  ___  ___  ___  ___  ___  _

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^5 + x\^3 + 
        x\^2\ \  + \ 1

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^5 + 
        x\^3

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ___  ___  ___  ___  ___

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^2\  + \ 1\)\)\)	
(note that  1 ≡ -1 mod 2,  
      2 ≡ 0 mod 2).
Continuing with the Euclidean algorithm, we have:
\(TraditionalForm\`\(\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \)\(x\^2

      x\^2 + 1\ \ \ \ \ \ \@\(x\^4\ \ \  + \ \ \ x\^2\)

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^4\ \ \ \  + \ \ x\^2

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ___  ___  __

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0\)\)\)
Thus c = GCD(a, a') = (x^2) + 1. 
w = a/c:
\(TraditionalForm\`\(\(
\)\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \)\(x\^8\ \  + x\^6\  + x\^3\  + 
        1

      x\^2 + 
        1\ \ \ \@\(x\^10\ \ \ \ \ \  + \ \ \ \ \ \ \ x\^6 + x\^5 + x\^3 + x\^2 + 1\)

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^10 + 
        x\^8

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ___  ___  ___  ___  ___  ___  ___  ___  __

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^8\ \ \  + \ x\^6\  + x\^5 + x\^3 + x\^2 + 1

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^8\ \ \  + \ x\^6

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ __\ \ \ \ ___  ___  ___  ___  ___  ___  _

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^5 + x\^3 + 
        x\^2\ \  + \ 1

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^5 + 
        x\^3

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ___  ___  ___  ___  ___

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^2\  + \ 1

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^2 + \ 1

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ___  ___

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0\)\)\)
so w = (x^8) + (x^6) + (x^3) + 1.
Now y = GCD(w, 
            c) = GCD((x^8) + (x^6) + (x^3) + 1,  (x^2) + 1):
\(TraditionalForm\`\(\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \)\(x\^6\ \  + x

      x\^2 + 
        1\ \ \ \@\(x\^8\ \ \  + \ \ x\^6\  + \ x\^3\ \ \ \ \ \ \ \ \ \ \ \ \  + \ 1\)

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^8\ \  + \ \ \ x\^6

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ___  ___  ___  ___  ___  ___  __

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^3\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  + 
        1

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^3\ \  + x

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ __\ \ \ \ ___  ___  ___  ___  __

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\ \ \ \ \  + \ \ 1\)\)\)
Continue with the division:
\(TraditionalForm\`\(\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \)\(x\ \ \  + \ 1

      x + 1\ \@\(x\^2\ \ \ \ \ \ \ \ \ \ \ \ \ \  + \ 1\)

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^2\  + x

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ___  ___  ___  _

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\ \ \ \ \  + \ 1

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\ \ \ \ \  + \ 1

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ___  ___  _

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0\)\)\)
So y = GCD(w, c) = 1 + x.  Thus the first factor z = w/
            y = (Subscript[a, 1]) = ((x^8) + (x^6) + (x^3) + 1)/(1 + x).
\(TraditionalForm\`\(\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \)\(x\^7 + x\^6\  + x\^2\  + x\ \  + \ 1

      x + 
        1\ \@\(x\^8\ \ \ \ \ \ \ \ \ \ \ \  + x\^6 + x\^3\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  + 1\)

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^8 + x\^7

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ___  ___  ___  ___  ___  ___  ___  __

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^7 + 
        x\^6

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^7 + 
        x\^6

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ___  ___  ___  ___  ___  ___  __

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^3\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  + 1

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^3 + x\^2

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ___  ___  ___  ___

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^2\ \ \ \ \ \ \ \ \ \ \  + 1

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\^2 + 
        x

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ___  ___  ___

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\ \  + \ 1

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x\ \  + \ 1

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ___  __

      \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0\)\)\)
So (Subscript[a, 1]) =  (x^7) + (x^6) + (x^2) + x + 1.

We have finished first iteration.  Now we enter second iteration for computation of (Subscript[a, 2]).   Let a = c = (x^2) + 1,  the new c = GCD(a, a') = GCD((x^2) + 1,  0) = 
            (x^2) + 1.   We are in trouble because the derivative of a (which is 2  x)  is zero  (in mod 2).   Thus we have to evoke step (6).   We write 
	a = ((x^2) + 1)  =  (((b(x)))^2),
and find the polynomial b(x).  Since a is quadratic, so b(x) must be linear.   There are only 4 linear polynomial in Z\(TraditionalForm\`\_2\), there are 0, 1, x, x + 1.   Clearly
(((1 + x))^2) ≡  
        (x^2) + 1  mod 2.  Since 1 + x can not be factored further, we conclude that (Subscript[a, 2]) = 1, and (Subscript[a, 3]) = (1 + x).   This is because old c during the first iteration (new a in second iteration) is c = (Subscript[a, 2]) ((Subscript[a, 3])^2).
The final result for square-free factorization is 
a(
          x)  =  ((x^7) + (x^6) + (x^2) + x + 1) (((x + 1))^3).