Tutorial: Pure Mathematics
Francis Wright, June 2018
Click on a problem header to show/hide my REDUCE solution.
- Use the Euclidean algorithm to compute \(\gcd(426,330)\).
- Find a solution to the equation \[ 426k + 330\ell = \gcd(426,330) \] where \(k\) and \(\ell\) are integers.
% This problem is not algebraic and we need integer Euclidean division, so... symbolic$ gcd(426, 330); % This implementation of the extended Euclidean algorithm % is based on Davenport, Siret & Tournier, page 214. q := 426; r := 330; qq := {1,0}; rr := {0,1}; while r neq 0 do << tmp := quotient(q,r); tt := {first qq - tmp*first rr, second qq - tmp*second rr}; tmp := remainder(q,r); q := r; r := tmp; qq := rr; rr := tt >>$ write "GCD = ", q$ write "{k,l} = ", qq$ % Check: 426*first qq + 330*second qq; algebraic$
Solve the following system of equations over
\(\mathbb{Z}_{11}\) for \(x\) and \(y\).
\[
\begin{eqnarray*}
[4]_{11} x + [7]_{11} y &=& [4]_{11} \\
[2]_{11} x + [6]_{11} y &=& [1]_{11}.
\end{eqnarray*}
\]
Check your answer.
setmod 11; on modular; eqns := {4x + 7y = 4, 2x + 6y = 1}; solve eqns; % Check: sub(ws, eqns); off modular;
Prove, using mathematical induction, that
\[ 12 \mid (7^n -3^{n+1} +2) \]
for all natural numbers \(n \ge 0\).
% First, explore the problem: operator d; let d(~n) => 7^n-3^(n+1)+2; for n := 0:5 collect d(n); for n := 0:5 collect remainder(d(n), 12); d(n+1) - d(n); % This is divisible by 12, because 7^n and 3^n must both be odd, so (7^n - 3^n) must be even. % Base case: d(0) = 0 is divisible by 12. % Induction step: Suppose 12|d(n). % Then 12|d(n+1) because d(n+1) = d(n) + 6(7^n - 3^n) and both summands are divisible by 12.
Let the operations of addition and multiplication on the set
\[ K = \{at+bu : a,b\in\mathbb{R}\}, \]
where \(t\) and \(u\) are formal symbols, be defined as follows:
\[
\begin{eqnarray*}
(at+bu)+(ct+du) &=& (a+c)t+(b+d)u, \\
(at+bu) \cdot (ct+du) &=& (ac+ad+bc-bd)t+(-ac+ad+bc+bd)u.
\end{eqnarray*}
\]
- Compute \((\frac12 t - \frac12 u)^2\) and express the result in the form \(at+bu\).
- Find a multiplicative identity in \(K\), and prove that the multiplication in \(K\) satisfies the identity law.
- Specify a bijection \(f : \mathbb{C}\to K\) such
that \(f(\alpha+\beta) = f(\alpha)+ f(\beta)\) and
\(f(\alpha\beta) = f(\alpha) f(\beta)\) for all
complex numbers \(\alpha\) and \(\beta\).
[Such a bijection is called an isomorphism of rings.]
% Two general elements of K are k1 := a*t+b*u$ k2 := c*t+d*u$ operator kplus, ktimes; let kplus(~k1,~k2) => (coeffn(k1,t,1)+coeffn(k2,t,1))*t + (coeffn(k1,u,1)+coeffn(k2,u,1))*u, ktimes(~k1,~k2) => begin scalar a,b,c,d; a := coeffn(k1,t,1); b := coeffn(k1,u,1); c := coeffn(k2,t,1); d := coeffn(k2,u,1); return (a*c+a*d+b*c-b*d)*t + (-a*c+a*d+b*c+b*d)*u end; % Check the above definitions: factor t, u; on div; kplus(k1,k2); ktimes(k1,k2); % (a) k3 := 1/2*t-1/2*u; ktimes(k3,k3); % (b) If k2 is a multiplicative identity for k1 then ktimes(k1,k2) = k1; lhs ws - rhs ws$ solve({coeffn(ws,t,1),coeffn(ws,u,1)}, {c,d}); % Hence the multiplicative identity in K is kid := sub(ws, k2); % (c) The obvious bijection would be that % (a + i*b) in C is equivalent to (a*t + b*u) in K: operator f; let f(~k) => coeffn(k,t,1) + coeffn(k,u,1)*i; % However... f(kplus(k1,k2)) = f(k1) + f(k2); % works f(ktimes(k1,k2)) = f(k1) * f(k2); % fails! % The bijection must be linear but more symmetric, so try let f(~k) => (coefn(k,t,1) + coefn(k,u,1)) + (coefn(k,t,1) - coefn(k,u,1))*i; f(kplus(k1,k2)) = f(k1) + f(k2); if f(kplus(k1,k2)) = f(k1) + f(k2) then true else false; f(ktimes(k1,k2)) = f(k1) * f(k2); if f(ktimes(k1,k2)) = f(k1) * f(k2) then true else false; % Check that f really is a bijection: f(k1) = c + i*d; lhs ws - rhs ws$ {coefn(ws,i,0), coefn(ws,i,1)}$ % i.e real and imaginary parts solve(ws, {a,b}); % which specifies k1 uniquely for any complex number (c + i*d). off div;