You are currently browsing the tag archive for the ‘euler’ tag.

I’ve previously written about Fermat’s Little Theorem, which tells us that if $latex p$ is a prime and $latex a$ is not divisible by $latex p$, then $latex a^{p-1} \equiv 1 \pmod{p}$.  That’s not terribly exciting when $latex p = 2$, so let’s concentrate on odd primes $latex p$ in this post.  Then $latex \frac{p-1}{2}$ is a whole number, so it makes sense (in the modular arithmetic world) to let $latex x = a^{\frac{p-1}{2}}$.  Then Fermat‘s Little Theorem tells us that $latex x^2 \equiv 1 \pmod{p}$.

How many possibilities for $latex x$ are there (modulo $latex p$, of course), if we know that $latex x^2 \equiv 1 \pmod{p}$?

Well, that congruence tells us that $latex (x – 1)(x + 1) \equiv 0 \pmod{p}$.  But, in the jargon, “there are no zero-divisors modulo a prime”.  That is, if $latex mn \equiv 0 \pmod{p}$, then $latex m \equiv 0 \pmod{p}$…

View original post 798 more words

I wrote this note in 2008 to introduce complex numbers. It is posted for the Math Teachers at Play blog carnival.

What is the ${\sqrt[4]{-16}}$?

In the set of Real Numbers, ${\mathbb{R}}$, the solution is undefined. We must consider the set of Complex Numbers, ${\mathbb{C}}$. Complex numbers are numbers of the form of ${a+bi}$, where ${a}$ and ${b}$ are real numbers: ${a,b\in\mathbb{R}}$ and ${i}$ is the imaginary unit. Note ${i}$ is defined by ${i^{2}=-1}$ or equivalently ${i=\sqrt{-1}}$.

Thus, we have:

$\displaystyle \begin{array}{rcl} \sqrt[4]{-16} & = & (-16)^{1/4}\\ & = & (-1\cdot16)^{1/4}\\ & = & (-1\cdot2^{4)^{1/4}}\\ & = & (-1)^{1/4}\cdot2^{4/4}\\ & = & (-1)^{1/4}\cdot2\\ & = & ((-1)^{1/2})^{1/2}\cdot2\\ & = & (\sqrt{-1})^{1/2}\cdot2\\ & = & i^{1/2}\cdot2\\ & = & 2\sqrt{i}.\end{array}$

We now have ${\sqrt[4]{-16}=2\sqrt{i}}$. So we must ask "What is the ${\sqrt{i}}$?". To evaluate ${\sqrt{i}}$ we will use Euler’s formula, ${e^{ix}=\cos\left(x\right)+i\sin\left(x\right).}$ So by substituting ${x=\frac{\pi}{2}}$, giving

$\displaystyle \begin{array}{rcl} e^{i(\frac{\pi}{2})} & = & \cos\left(\frac{\pi}{2}\right)+i\sin\left(\frac{\pi}{2}\right)\\ & = & 0+i(1)\\ & = & i.\end{array}$

Note we have isolated ${i}$ and now arrived at the following equality: ${i=e^{i(\frac{\pi}{2})}}$. Taking the square root of both sides gives

$\displaystyle \begin{array}{rcl} \sqrt{i} & = & \sqrt{e^{i(\frac{\pi}{2})}}\\ & = & e^{i(\frac{\pi}{2})(\frac{1}{2})}\\ & = & e^{i(\frac{\pi}{4})}.\end{array}$

Thus, we have now have ${\sqrt{i}=e^{i(\frac{\pi}{4})}}$ and following through application of Euler’s formula to ${x=\frac{\pi}{4}}$, gives

$\displaystyle \begin{array}{rcl} \sqrt{i} & = & e^{i(\frac{\pi}{4})}\\ & = & \cos\left(\frac{\pi}{4}\right)+i\sin\left(\frac{\pi}{4}\right)\\ & = & \frac{1}{\sqrt{2}}+i(\frac{1}{\sqrt{2}})\\ & = & \frac{\sqrt{2}}{2}+i(\frac{\sqrt{2}}{2})\\ & = & \frac{\sqrt{2}+\sqrt{2}i}{2}.\end{array}$

So going back to the original problem and substituting ${\sqrt{i}=\frac{\sqrt{2}+\sqrt{2}i}{2}}$, gives

$\displaystyle \begin{array}{rcl} \sqrt[4]{-16} & = & 2\sqrt{i}\\ & = & 2(\frac{\sqrt{2}+\sqrt{2}i}{2})\\ & = & \sqrt{2}+\sqrt{2}i.\end{array}$

Hence, the solution, ${\sqrt[4]{-16}=\sqrt{2}+\sqrt{2}i}$ , is a complex number!

Proofs from THE BOOK by Martin Aigner and Günter Ziegler begins by giving six proofs of the infinity of primes. We will go over the third proof. Before we go over this proof, lets cover some background.

— 1. Fermat Numbers —

Fermat numbers are defined by

$\displaystyle F_{n}=2^{2^{n}}+1,$

so that ${F_{0}=3,F_{1}=5,F_{2}=17,F_{3}=257,}$ and ${F_{4}=65537}$. They are of great interest in many ways: for example, it was proved by Gauss that, if ${F_{n}}$, is a prime ${p}$, then a regular polygon of ${p}$ sides can be inscribed in a circle by Euclidean methods. The property of the Fermat numbers which is relevant here is

Theorem 1 No two Fermat numbers have a common divisor greater than 1.

We will prove this theorem later.

The first four Fermat numbers are prime, and Fermat conjectured that all were prime. Euler, however, found in 1732 that

$\displaystyle F_{5}=2^{2^{5}}+1=641\cdot6700417$

is composite.

In 1880 Landry proved that

$\displaystyle F_{6}=2^{2^{6}}+1=274177\cdot67280421310721.$

It is currently known that ${F_{n}}$, is composite for ${5 \leq n \leq 32}$. Factoring Fermat numbers is extremely difficult as a result of their large size. ${F_{12}}$ has ${5}$ known factors with ${C1187}$ remaining (where ${C}$ denotes a composite number with $n$ digits). ${F_{13}}$ has ${4}$ known factors with ${C2391}$ remaining. ${F_{14}}$ has no known factors but is composite. There are currently four Fermat numbers that are known to be composite, but for which no single factor is known: ${F_{14},F_{20},F_{22},}$ and ${F_{14}}$. In all the other cases proved to be composite a factor is known. No prime ${F_{n}}$ has been found beyond ${F_{4}}$, and it seems unlikely that any more will be found using current computational methods and hardware.

— 2. Infinitude of Primes Theorem —

We are now ready to prove Euclid’s Second Theorem, also called the Infinitude of Primes Theorem using the third proof in Proofs from THE BOOK.

Theorem 2 (Euclid’s Second Theorem) The number of primes is infinite.

Proof: Next let us look at the Fermat numbers ${F_{n}=2^{2^{n}}+1}$ for ${n=0,1,2,\cdots}$. We will show that any two Fermat numbers are relatively prime (Theorem 1); hence there must be infinitely many primes. To this end, we verify the recursion

$\displaystyle \prod_{k=0}^{n-1}F_{k}=F_{n}-2\quad(n\geq1),$

from which our assertion follows immediately. Indeed, if ${m}$ is a divisor of, say, ${F_{k}}$ and ${F_{n}}$ ${(k, then ${m}$ divides ${2}$, and hence ${m=1}$ or ${2}$. But ${m=2}$ is impossible since all Fermat numbers are odd.

To prove the recursion we use induction on ${n}$. For ${n=1}$ we have ${F_{0}=3}$ and ${F_{1}-2=5-2=3}$. With induction we now conclude

$\displaystyle \begin{array}{rcl} \prod_{k=0}^{n} F_{k} & = & \left(\prod_{k=0}^{n-1}F_{k}\right)F_{n}\\ & = & (F_{n}-2)F_{n}\\ & = & (2^{2^{n}}-1)(2^{2^{n}}+1)\\ & = & 2^{2^{n+1}}-1\\ & = & F_{n+1}-2. \Box \end{array}$

Proofs from THE BOOK by Martin Aigner and Günter Ziegler begins by giving six proofs of the infinity of primes. We will go over the second proof. Before we go over this proof, lets cover some background.

— 1. Algebraic Structures —

One of the themes of modern algebra is to compare algebraic structures. An algebraic structure refers to a nonempty set equipped with a binary operation or several binary operations (usually two). Also, we shall refer to a nonempty set equipped with two binary operations satisfying certain properties as a number system. First, we shall define algebraic structures called group, ring and field. A group consists of nonempty set with one binary operation satisfying several conditions. It is the simplest of the three.

Definition 1 Let ${G}$ be a nonempty set and ${*:G\times G\rightarrow G}$ be a binary operation on ${G.}$ Then the set ${G}$ together with the binary operation ${*}$, denoted${(G,*)}$, is a group, if the following three conditions are satisfied:

i. The binary operation ${*}$ is associative, i.e., ${(a*b)*c=a*(b*c)}$ for all ${a,b,c\in G}$.

ii. There is a ${*}$-identity ${e\in G}$, i.e., ${e*x=x*e=x}$ for all ${x\in G}$.

iii. For each ${a\in G}$, there is a ${*}$-inverse ${a'\in G}$, i.e., ${a*a'=a'*a=e}$, where ${e}$ is the ${*}$-identity.

Further more, a group ${(G,*)}$ is said to be commutative (or abelian), if the binary operation ${*}$ is commutative.

Euler Formula

The Euler formula, sometimes also called the Euler identity, states

$\displaystyle e^{ix}=cosx+isinx,$

where ${i}$ is the imaginary unit. Note that Euler’s polyhedral formula is sometimes also called the Euler formula, as is the Euler curvature formula.

The special case of the formula with ${x=\pi}$ gives the beautiful identity

$\displaystyle e^{i\pi}=-1,$

an equation connecting the fundamental numbers ${i,\pi,e,1,}$ and ${0}$, the fundamental operations ${+}$, ${\times}$, and exponentiation, the most important relation ${=}$, and nothing else. Gauss is reported to have commented that if this formula was not immediately obvious, the reader would never be a first-class mathematician.