Monthly Archive

You are currently browsing the monthly archive for February 2012.

Theorem 39: Euler’s criterion

February 26, 2012 in WordPress Links | Tags: carmichael numbers, euler, euler's criterion, fermat, fermat's little theorem, legendre, legendre symbol, modulo, prime numbers, quadratic residue, residue, solovay-strassen primality test, theorem of the week, wordpress, zero-divisors | Leave a comment

http://theoremoftheweek.wordpress.com

Theorem of the week

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

How It Works

February 18, 2012 in Mathematics Posts | Tags: comics, humor, math, xkcd | Leave a comment

xkcd

47th edition of the Math Teachers at Play Blog Carnival

February 17, 2012 in WordPress Links | Tags: blog carnival, math hombre, math teachers at play, teachers, wordpress | Leave a comment

The 47th edition of the Math Teachers at Play Blog Carnival is now up at Math Hombre. Check it out!

Five Lemma in Blackboard Beamer Theme

February 16, 2012 in Mathematics Posts | Tags: apple keynote, beamer, blackboard theme, commutative diagram, diagram chasing, epimorphism, exact sequences, five lemma, free modules, homological algebra, homomorphism, latex, modules, monomorphism, morphisms, presentation slides, r-module | 5 comments

Using Blackboard beamer theme version 0.2 I can create presentation slides that imitate the Apple’s Keynote Blackboard theme and I get to use LaTex which gives me full power to present any mathematical formula I desire!

When creating my first latex presentation slides, using the blackboard beamer theme, I found these two websites helpful.

Introduction to Beamer:
http://www.mathematik.uni-wuerzburg.de/~gerdts/beamer_intro.pdf

Making Presentations with LaTeX Guidelines:
http://xavier.perseguers.ch/fileadmin/download/LaTeX/guidelines.pdf

Here is my presentation:

Attention Bloggers: We Want You!

February 13, 2012 in WordPress Links | Tags: activities, blog carnival, games, math hombre, math teachers at play, mathematics, precollege, preschool, teachers, wordpress | Leave a comment

Activities, games, lessons, hands-on fun — the Math Teachers at Play blog carnival would love to feature your article about mathematics from preschool to precollege level (through the first year of calculus). You can submit your article online, or email John directly to make sure he gets your submission.

Deadline: This Wednesday night!
The carnival will be published Friday at Math Hombre.

Attention Bloggers: We Want You!.

A Complex Problem

February 13, 2012 in Mathematics Posts | Tags: blog carnival, complex numbers, euler, euler's formula, math teachers at play, mathematics, precollege, roots | Leave a comment

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!

Understanding Negative Numbers

February 13, 2012 in Mathematics Posts | Tags: blog carnival, math hombre, math teachers at play, negative numbers, precollege, teachers | 1 comment

I wrote this note in 2008 to give a down-to-earth example to help in the understanding of negative numbers [2]. It is posted for the Math Teachers at Play blog carnival.

— 1. Introduction —

First, lets get all the formalities out of the way by observing a few algebraic rules regarding positive and negative real numbers. We will consider the familiar arithmetic operations of addition and multiplication [3]. Feel free to skip over this section and continue to section.

— 1.1. Rules Addition (Sum) —

Rules for adding any two real numbers ${a}$ , ${b}$

The result of addition is called the sum.
The sum between ${a}$ and ${b}$ is indicated as:
$\displaystyle a+b$
If ${a}$ and ${b}$ are both positive, then the sum is positive.
$\displaystyle 4+3=7$
If ${a}$ and ${b}$ are both negative, then the sum is negative.
$\displaystyle -4+(-3)=-7$
If ${a}$ is positive and ${b}$ is negative and ${|a|>|b|}$ , then the sum is positive.
$\displaystyle 4+(-3)=1$
If ${a}$ is positive and ${b}$ is negative and ${|a|<|b|}$ , then the sum is negative.
$\displaystyle 3+(-4)=-1$
Addition is commutative: ${a+b=b+a}$ .
$\displaystyle 4+3=3+4=7$
Addition is associative: ${a+(b+c)=(a+b)+c}$ .
$\displaystyle 1+(2+4)=(1+2)+4=7$
${a+(-b)=a-b}$ .
${a+(-a)=0}$ ; ${a+0=a}$ .

— 1.2. Rules Multiplication (Product) —

Rules for multiplying any two real numbers ${a}$ , ${b}$

The result of multiplication is called the product.
The product between ${a}$ and ${b}$ is indicated as:
$\displaystyle a\times b=a\cdot b=a(b)=(a)b=(a)(b)=ab$
If a and b have the same sign, then the product is positive.
$\displaystyle (4)(3)=12$

$\displaystyle (-4)(-3)=12$
If a and b have opposite signs, then the product is negative.
$\displaystyle (-4)(3)=-12$

$\displaystyle (4)(-3)=-12$
Distributive property: ${a(b+c)=ab+ac}$ ; ${a(b-c)=ab-ac}$ .
$\displaystyle 4(2+1)=8+4=12$

$\displaystyle 4(2-1)=8-4=4$
Multiplication is commutative: ${ab=ba}$ .
$\displaystyle (4)(3)=(3)(4)=12$
Multiplication is associative: ${a(bc)=(ab)c}$ .
$\displaystyle 1(2\cdot6)=(1\cdot2)6=12$
The product of any real number and -1 is the additive inverse of the real number.
$\displaystyle (-1)a=-a$

$\displaystyle (-1)(-1)=-(-1)=1$

$\displaystyle (-a)(-b)=(-1\cdot a)(-1\cdot b)=(-1)(-1)(a)(b)=1(ab)=ab$
${a\cdot1=1\cdot a=a}$ ; ${a\cdot0=0\cdot a=0}$ .

— 2. Example —

Why is a negative times a negative a positive? Many people have trouble answering this question. While, most will not have an issue memorizing the rule. Understanding the reasoning for the rule is another matter. Many people try to come up with a visualization to help picture what is going on [1]. We shall use money to illustrate the concept. When going over the example try to think of a negative as a loss and a positive as a gain.

— 2.1. The Offer You Can’t Refuse —

Well, you asked for it!

Suppose your are bankrupt. You now own ${\$0}$ dollars. You approach Mr. Mob Boss for a loan of ${\$4,000}$ dollars. He does so with the condition that you pay him back 4 times that amount. You now have a debt of

$\displaystyle 4\cdot-\$4,000=-\$16,000$

See rule 1.2.4 for reference.

In other words, you owe Mr. Mob Boss ${4}$ debts of ${\$4,000}$ . You have lost ${\$16,000}$ dollars. You take the ${\$4000}$ and invest it all in starting an Italian restaurant. The problem is all your customers are members of La Cosa Nostra, who expect nothing less than a free meal with the finest wine.

Eventually realizing you will never break even, you approach Mr. Mob Boss to tell him the bad news. Unexpectedly, he is so happy about the service you provide that he decides to forgive your ${4}$ debts of ${\$4,000}$ !

$\displaystyle -4\cdot-\$4,000=\$16,000$

See rule 1.2.3 for reference.

You have gained ${\$16,000}$ dollars, and, thus, you are back where you started…absolutely broke! However, try not to be so "negative". At least you have a job for the rest of your life.

Fuggid about it!

References

[1] Dr. Math, Negative x negative = positive, available at http://mathforum.org/dr.math/faq/faq.negxneg.html.
[2] Ian Stewart, Letters to a young mathematician, first ed., Basic Books, 2006.
[3] Rong Yang, A-plus notes for algebra: With trigonometry and probability, third ed., A-Plus Notes Learning Center, 2000.

The Salamander Lemma – On diagram-chasing in double complexes

February 11, 2012 in Mathematics Posts | Tags: 3×3-lemma, abelian category, anton geraschenko, categories, chain complexes, cokernel, complex, connecting morphism, diagram chasing, double complex, exact sequences, exactness, george bergman, homological algebra, homology, horizontal homology, image, kernel, morphisms, salamander lemma, snake lemma, vertical homology | Leave a comment

Back in November 2007 Anton Geraschenko had an interesting post at the Secret Blogging Seminar based on a preprint by George Bergman. His original preprint is now on the arXiv, where this is an updated version accepted by journal Theory and Applications of Categories, reformatted with their cls file. Old Lemma 12 dropped (referee noted it was immediate consequence of Lemma 11); some typos fixed, and wording cleaned up. Homological algebra is full of diagram chasing arguments.

Here is an introduction to his paper:
Diagram-chasing arguments frequently lead to “magical” relations between distant points of diagrams: exactness implications, connecting morphisms, etc.. These long connections are usually composites of short “unmagical” connections, but the latter, and the objects they join, are not visible in the proofs. I try to remedy this situation.
Given a double complex in an abelian category, we consider, for each object $A$ of the complex, the familiar horizontal and vertical homology objects at $A$ , and two other objects, which we name the “donor” $A_\Box$ and and the “receptor” ${^\Box}A$ at $A$ . For each arrow of the double complex, we prove the exactness of a 6-term sequence of these objects (the “Salamander Lemma”). Standard results such as the 3×3-Lemma, the Snake Lemma, and the long exact sequence of homology associated with a short exact sequence of complexes, are obtained as easy applications of this lemma.
We then obtain some generalizations of the last of the above examples, getting various exact diagrams from double complexes with all but a few rows and columns exact.
The total homology of a double complex is also examined in terms of the constructions we have introduced. We end with a brief look at the world of triple complexes, and two exercises.

Math Paper

February 10, 2012 in Mathematics Posts | Tags: comics, humor, math, xkcd | Leave a comment

xkcd

The Snake Lemma

February 10, 2012 in Mathematics Posts | Tags: abelian category, categories, chain complexes, cokernel, commutative diagram, complex, connecting morphism, diagram chasing, exact sequences, exactness, five lemma, four lemma, groups, homological algebra, homomorphism, homotopy, image, it's my turn, kernel, modules, morphisms, movie, nine lemma, sheaves, snake lemma, zig-zag lemma | Leave a comment

Diagram chasing is a method of mathematical proof used especially in homological algebra. Homological algebra studies, in particular, the homology of chain complexes in abelian categories – therefore the name. From a modern perspective, homological algebra is the study of algebraic objects, (such as groups, rings or Lie algebras, or sheaves of such objects), by ‘resolving them’, replacing them by more stable objects whose homotopy category is the derived category of an abelian category. Given a commutative diagram, a proof by diagram chasing involves the formal use of the properties of the diagram, such as injective or surjective maps, or exact sequences. A syllogism is constructed, for which the graphical display of the diagram is just a visual aid. It follows that one ends up "chasing" elements around the diagram, until the desired element or result is constructed or verified. Examples of proofs by diagram chasing include those typically given for the Snake Lemma, Four Lemma, Five Lemma, Nine Lemma, and Zig-Zag Lemma.

Definition 1 An exact sequence is a sequence, either finite or infinite, of objects and morphisms between them such that the image of one morphism equals the kernel of the next.

Definition 2 A short exact sequence is a finite sequence of objects and morphisms between them such that the image of one morphism equals the kernel of the next.

Definition 3 A long exact sequence is an infinite sequence of objects and morphisms between them such that the image of one morphism equals the kernel of the next.

Formally, an exact sequence is a sequence of maps

$\displaystyle \alpha_{i}:A_{i}\rightarrow A_{i+1}$

between a sequence of spaces ${A_{i},}$ which satisfies

$\displaystyle im(\alpha_{i})=\ker(\alpha_{i+1}),$

where ${im}$ denotes the image and ${\ker}$ the group kernel. That is, ${a\in A_{i},\alpha_{i}(a)=0}$ iff ${a=\alpha_{i-1}(b)}$ for some ${b\in A_{i-1}}$ . It follows that ${\alpha_{i+1}\circ\alpha_{i}=0.}$ The notion of exact sequence makes sense when the spaces are groups, modules, chain complexes, or sheaves. The notation for the maps may be suppressed and the sequence written on a single line as

$\displaystyle \cdots\rightarrow A_{i-1}\rightarrow A_{i}\rightarrow A_{i+1}\rightarrow\cdots.$

A short exact sequence:
$\displaystyle 0\rightarrow A\rightarrow B\rightarrow C\rightarrow0.$

beginning and ending with zero, meaning the zero module ${\{0\}}$ .
A long exact sequence:
$\displaystyle \cdots\rightarrow A\rightarrow B\rightarrow C\rightarrow\cdots.$

Special information is conveyed when one of the spaces is the zero module. For instance, the sequence

$\displaystyle 0\rightarrow A\rightarrow B$

is exact iff the map is injective. Similarly,

$\displaystyle A\rightarrow B\rightarrow0$

is exact iff the map is surjective.

In homological algebra, given a short exact sequence ${0\rightarrow M'\rightarrow M\rightarrow M''\rightarrow0}$ of ${G}$ -modules, there is a canonical long exact sequence

$\displaystyle 0\rightarrow H^{0}(G,M')\rightarrow\cdots\rightarrow H^{i}(G,M'')\stackrel{\delta_{i}}{\rightarrow}H^{i+1}(G,M')\rightarrow \\ H^{i+1}(G,M)\rightarrow H^{i+1}(G,M'')\cdots,$

where the ${\delta_{i}}$ are certain "connecting homomorphisms" (or "snake maps"). This can be deduced from the Snake Lemma. For the proof the latter, one can engage in "diagram chasing". One can see, in the movie It’s My Turn (1980) a proof given for the Snake Lemma using diagram chasing. To define ${\delta}$ : given ${x''\in\ker(\gamma)\subseteq C}$ , lift ${x}$ " to ${B}$ , push it into ${B'}$ by ${\beta}$ , then check that the image has a preimage in ${A'}$ . Then verify that the result is well-defined, et cetera.

Lemma 1 (Snake Lemma) Given the commuting diagram

in which the rows are exact, there is a canonical map ${\delta:\ker(\gamma)\rightarrow coker(\alpha)}$ , induced by ${\delta x''=f'^{-1}\circ\beta\circ g^{-1}x''}$ such that the sequence

$\displaystyle 0\rightarrow\ker(\alpha)\rightarrow\ker(\beta)\rightarrow\ker(\gamma)\stackrel{\delta}{\rightarrow} coker(\alpha)\rightarrow coker(\beta)\rightarrow \\ coker(\gamma)\rightarrow0$

is exact.

Proof: Suppose we are given a commutative diagram

with exact rows. We wish to prove that the sequence

$\displaystyle 0\rightarrow\ker(\alpha)\rightarrow\ker(\beta)\rightarrow\ker(\gamma)\rightarrow coker(\alpha)\rightarrow coker(\beta)\rightarrow \\ coker(\gamma)\rightarrow0$

is exact.

First we claim that if any square

is commutative, then there are well-defined morphisms ${\ker(\varphi)\rightarrow\ker(\psi)}$ and ${ coker(\varphi)\rightarrow coker(\psi)}$ . For example, if ${x\in\ker(\varphi)}$ , then the square

must commute, and so the image of ${x}$ in the top row must be in ${\ker(\psi)}$ . The proof of the claim for cokernels is similar. Thus we have two sequences,

$\displaystyle 0\rightarrow\ker(\alpha)\rightarrow\ker(\beta)\rightarrow\ker(\gamma){\ and\ } coker(\alpha)\rightarrow coker(\beta)\rightarrow \\ coker(\gamma)\rightarrow0,$

each of which inherits being a complex from the original diagram.

Suppose ${x\in\ker(\beta)}$ is sent to ${0\in\ker(\gamma)}$ . By exactness, ${x}$ has a preimage ${x'\in A}$ . Because the diagram

is commutative and the bottom morphism is injective, ${y'=0}$ and so ${x'\in\ker(\alpha)}$ . So the sequence

$\displaystyle 0\rightarrow\ker(\alpha)\rightarrow\ker(\beta)\rightarrow\ker(\gamma)$

is exact. The proof of the claim for the cokernel sequence is similar.

So now all we need to do is find a connecting morphism ${\ker(\gamma)\rightarrow coker(\alpha)}$ such that the resulting sequence is exact at both of those points.

Suppose ${x''\in\ker(\gamma)}$ . Then ${x''}$ has at least one preimage in ${B}$ . So let ${x}$ and ${\widehat{x}}$ be preimages of ${x''}$ . Thus ${\widehat{x}-x\mapsto0}$ and so by exactness has a preimage ${x'\in A}$ . By commutativity of the diagram, ${\beta(x)}$ has a preimage ${y'}$ , which is unique by injectivity of the morphism ${A'\rightarrow B'}$ . But we know that the square

is commutative. We wish to define ${\ker(\gamma)\rightarrow coker(\alpha)}$ by ${x''\mapsto y'+im(\alpha)}$ . Observe that

$\displaystyle y'+\alpha(x')\mapsto\beta(x)+\beta(\widehat{x}-x)=\beta(\widehat{x}),$

and so the choice of preimage of ${x''}$ does not affect which cokernel element we ultimately select. So now we have our connecting morphism. By applying this definition we see that

$\displaystyle \ker(\beta)\rightarrow\ker(\gamma)\rightarrow coker(\alpha)\rightarrow coker(\beta)$

is a complex.

Suppose ${x''\in\ker(\gamma)}$ is sent to ${0}$ by the connecting morphism. Thus we have a diagram

which is commutative. Let ${\widehat{x}}$ be the image of ${x'}$ under the morphism ${A\rightarrow B}$ . Exactness of the diagram implies that ${x-\widehat{x}}$ is a preimage of ${x''}$ . But ${\beta(x-\widehat{x})=0}$ . So the kernel-cokernel sequence is exact at ${\ker(\gamma)}$ . The proof that it is exact at ${coker(\alpha)}$ is similar.