Algebra and proof practice: six original exercises

How to choose a method

• A statement is indexed by every integer n starting at a fixed value: consider induction. First see whether a direct proof is simpler.
• You need $\gcd(a,b)$, or integers u and v with $au+bv=\gcd(a,b)$: use the Euclidean algorithm and back-substitution.
• You need all integer solutions of $ax+by=c$: check the gcd divisibility condition before searching for solutions.
• You need a remainder or a congruence solution: reduce modulo m; check invertibility before dividing.
• You need a complex quotient: multiply by the denominator's conjugate. For powers or roots, polar form is often simpler.

Throughout, integers are elements of $\mathbb{Z}$. The notation $a \mid b$ means $b=ak$ for some integer k. Congruences use a positive integer modulus greater than 1.

1 Proving a statement by induction

To prove $P(n)$ for all integers $n\ge n_{0}$, establish $P(n_{0})$, then show that $P(k)$ implies $P(k+1)$ for an arbitrary integer $k\ge n_{0}$. The induction hypothesis is an assumption used inside that implication; it is not permission to assume the conclusion.

For a complete worked proof, review the induction method, then check the starting index and base case.

Check your proof. Did you name the starting value, state the hypothesis, use it, and finish with the exact expression required at $k+1$? Checking several numerical cases is useful for spotting errors, but does not prove a statement for infinitely many n.

2 Greatest common divisors and Bézout identities

For integers $a,b$ not both zero, $\gcd(a,b)$ is their greatest positive common divisor. Bézout's identity states that there are integers $u,v$ such that $au+bv=\gcd(a,b)$.

The Euclidean algorithm works because $a=qb+r$ implies $\gcd(a,b)=\gcd(b,r)$: a divisor of both a and b divides $r=a-qb$, and a divisor of both b and r divides $a=qb+r$.

Worked example

Find $\gcd(252,198)$ and a Bézout identity:

The last nonzero remainder is 18. Back-substitute:

Thus $\gcd(252,198)=18$, with $u=4$ and $v=-5$. The final equality also gives a quick arithmetic check: $1008-990=18$.

3 Linear Diophantine equations

A linear Diophantine equation $ax+by=c$ asks for integer solutions $x,y$. For positive integers $a,b$, let $d=\gcd(a,b)$. Solutions exist exactly when $d \mid c$.

Why the condition is necessary. Since d divides a and b, it divides every integer combination $ax+by$, hence must divide c.

Why it is sufficient. A Bézout identity $au+bv=d$, multiplied by $c/d$, gives a solution when $d \mid c$.

From one solution $(x_{0},y_{0})$, every solution is

To see completeness, subtract the equations for two solutions and divide by d. The resulting coprime coefficients imply that $b/d$ divides $x-x_{0}$; substituting this difference forces the stated change in y.

Worked example

Solve $14x+21y=35$. Here $d=7$ divides 35. Divide by 7 to obtain $2x+3y=5$. One solution is $(1,1)$, so all solutions are

Substitution gives $2(1+3t)+3(1-2t)=5$. If x and y must also be nonnegative, the inequalities $t\ge -1/3$ and $t\le 1/2$ leave only $t=0$. The only nonnegative solution is $(1,1)$.

4 Congruences and legitimate cancellation

The statement $a\equiv b \pmod{m}$ means $m \mid (a-b)$. Addition and multiplication preserve congruences. Division needs care: a has a multiplicative inverse modulo m exactly when $\gcd(a,m)=1$.

More generally, $ax\equiv b \pmod{m}$ has a solution exactly when $\gcd(a,m)$ divides b. If $d=\gcd(a,m)$ divides b and $d=m$, every integer x is a solution. If d divides b and $d<m$, divide $a,b$ and m by d to get an equivalent congruence modulo $m/d>1$. Keeping the original modulus after cancellation can lose solutions.

Worked example

Solve $7x\equiv 5 \pmod{12}$. Since $7\times 7=49\equiv 1 \pmod{12}$, multiply by 7:

Check: $7\times 11-5=72$, a multiple of 12. All integer solutions are $x=11+12t$, $t\in \mathbb{Z}$.

Cancellation warning. From $2x\equiv 2 \pmod{6}$, the correct reduced statement is $x\equiv 1 \pmod{3}$. Modulo 6 this gives two residues, 1 and 4. Writing only $x\equiv 1 \pmod{6}$ misses a solution.

5 Complex arithmetic and roots

A complex number is $z=a+bi$ with $a,b$ real and $i^{2}=-1$. Its conjugate is $\overline{z}=a-bi$ and its modulus is $\lvert z\rvert=\sqrt{a^2+b^2}$. Thus $z\overline{z}=\lvert z\rvert^2$.

For powers and roots, review Cartesian and polar forms, De Moivre’s formula and how to find every root. Use those methods in Exercise 6 below.

Worked example

Simplify $(2-i)/(1+i)$. Multiply numerator and denominator by $1-i$:

Check by multiplying the answer by $1+i$; it returns $2-i$. For roots, also check that you have the required number of distinct answers and that each has the correct modulus.

Six original practice exercises

Try these before reading the solutions. The points are a suggested self-assessment rubric, not an official Waterloo grading scheme.

More practice: Waterloo MATH135, Fall 2009

These Waterloo papers are from Fall 2009. Choose questions on topics covered in your current course.

Useful direct links:

• Term Test 1: Question 2 for induction; Question 5(a) for the Euclidean algorithm and a Bézout identity. Official solutions.
• Final exam: Question 2(b) for integer equations; Question 3(b) for simultaneous congruences; Question 7 for complex numbers. Official solutions.

Try a question before opening its solution. Compare the reasoning, then redo any step you could not justify on your own.

Choose your next step

Start with a concept or one of these exercises. If you have an attempt, you can use it to show where you got stuck. Get help with proofs and discrete mathematics.