# Examples of proofs that use a cycle of implications to prove equivalence

I'm looking for some examples of proofs where it's easier to prove 'cyclical implications' $A\implies B\implies C\implies A$ than to prove $A\iff B$ directly.

I can think of some (relatively) advanced examples — but I'm looking for examples accessible to (ordinary) high-school students.

• My linear algebra textbook does a lot of that. But I bet that's the advanced example you don't want. – Sue VanHattum Jan 9 '15 at 1:58
• An example from graph theory is to prove the equivalence of various definitions of trees: en.wikipedia.org/wiki/Tree_%28graph_theory%29#Definitions. This is done in Harary's book: books.google.com/books/about/Graph_Theory.html?id=9nOljWrLzAAC – M. Vinay Jan 9 '15 at 2:43
• Are linear systems and matrices a part of high school curricula where you teach? If so, the usual set of equivalent conditions for a matrix being invertible might be a good example. – GPerez Jan 10 '15 at 0:39
• If they know about complex numbers, maybe you could use something along the lines of $x-a$ divides $p(x)$ if $p(a) = 0$ if $p(a^*) =0$ if $x-a^*$ divides $p(x)$? – Alexander Gruber Jan 10 '15 at 18:50
• What mathematical background do you want to assume of your ordinary high school student? – KCd Jan 14 '15 at 9:34

Proving equivalent the below characterizations of squarefree naturals is quite elementary employing cyclic inferences (assuming one knows the existence and uniqueness of prime factorizations).

Theorem $\$ The following are equivalent for a natural number $\,q > 1$

$(1)\qquad\quad n^2\!\nmid q\,\$ for all naturals $\,n > 1$

$(2)\qquad\quad p^2\!\nmid q\ \$ for all primes $\,p$

$(3)\qquad\quad q\,$ is a product of distinct primes

$(4)\qquad\quad q\mid n^k\Rightarrow\, q\mid n\,\$ for all naturals $\,n,k$

Proof $\$ All $\,(n)\Rightarrow (n\!+\!1)$ are obvious. $\,(4)\,\Rightarrow\,(1)\,$ may be proved as follows

$\qquad\ \$ If $\ q = an^2\,$ then $\ q\mid (an)^2\,\overset{ (4)}\Rightarrow\ q\mid an\,\Rightarrow\,an^2\mid n\,\Rightarrow\,n=1$

Remark $\$ For further characterizations see here, which includes the little known $\, q^q\!\mid n^n\Rightarrow\, q\mid n$

• very nice — and exactly on the level I had in mind. thank you! – Grigory M Jan 27 '15 at 19:15

## Geometry

The following two theorems came from Sonoma.

If a line intersects two lines then the following conditions are equivalent.

1. The alternate interior angles are the same size.
2. The corresponding angles are the same size.
3. The opposite interior angles are supplementary.

If two lines are crossed by a third, then the following conditions are equivalent.

1. The alternate interior angles are the same size.
2. The corresponding angles are the same size.
3. The opposite interior angles are supplementary.
4. The two lines are parallel.

## Algebra

I am not sure what to think of the difficult of this one but it could be explainable.

Let $p\geq 2$ be an integer. Then the following conditions are equivalent.

1. $p$ is prime.
2. For any $a\neq 0\in\mathbb{Z}_p$, the equation $ax=1$ has a solution in $\mathbb{Z}_p$.
3. Whenever $ab=0$ in $\mathbb{Z}_p$, then $a=0$ or $b=0$ in $\mathbb{Z}_p$.

Let $\mathbf{A}$ be an $n\times n$ matrix. Then the following are equivalent. (Note you could make this for only $2\times 2$ matrices so it isn't over the head of the students.)
1. $\mathbf{A}$ is row equivalent to $\mathbb{I}$
2. $\mathbf{A}$ is a product of elementary matrices
3. $\mathbf{A}$ is invertible
4. The system $\mathbf{Ax}=\mathbf{0}$ has only the trivial solution
5. For any $n$ dimensional vector $\mathbf{b}$, the system $\mathbf{Ax}=\mathbf{b}$ has a unique solutions.