Number Theory and Polynomial Background for the Decomposition Theorem

OK so what’s a natural number….. First off, the set of naturals gets written like , but the old equation editor doesn’t do that fancy blackboard-bold thing, so I’ll just write it as N. And — something like that works fine.

Same deal with integers. The integer set is written as , and same as before, I’ll just write Z from here on.

You can write something like this.

Now here’s the thing about integers, unlike the naturals: inside Z, addition, subtraction, and multiplication are free. You can do them all and stay inside Z. (Division is NOT free!!!!)

OK OK OK OK, didn’t I just say multiplication is free in Z?! So then — if a = bc, naturally b is a divisor of a, right??? To say “b is a divisor of a~~”, we write b|a~!! Catch this notation.

Another property of the integers: I’m going to write division like this. There’s a property hiding in here.

100 ÷ 17 = 5 ····· 15

When you express division like this — what do you call it, “elementary school division” (?) lol — when you write it that way, let me put it in general terms. Writing a = bq + r with b > 0, the property in Z is that q and r exist and are unique (with 0 ≤ r < b).

Sets of multiples

Hmm, I kind of skirted around the concept of ‘multiples’ above….. Sorry. Let’s just assume we already know what a multiple is (we all know, right? ^^ heh heh heh). Then I’ll write the ‘set of multiples of 2 (the even numbers)’ like this.

Yo!!! Slick!!! The ‘set of multiples of n’ can also be written like this?!

The set of multiples of n has this property: if na, nb ∈ nZ (⊆ Z), then na ± nb, na × nb ∈ nZ.

I’ve been a bit all-over-the-place above, but now you probably see why I suddenly started talking about these multiple-sets!! Right!? The set nZ is closed under +, −, and ×!!!

OK so let’s flip it!!!!

If a nonempty A ⊆ Z is closed under +, −, ×, can we claim A has the form nZ~~~?!

Answer: YES!!!!

Here’s why. If A = {0}, it’s already 0Z. Otherwise A contains a positive element (flip the sign if needed), so let n be its smallest positive element. Didn’t I say A is closed under addition???? Then n + n = 2n ∈ A, and 3n ∈ A. Going on like this — I can’t say what else is in A, but every multiple of n is definitely in there!! heh heh heh So we can write ’nZ ⊂ A’!!! Nice!~

For now, A is a bit bigger than nZ?! So suppose there’s some m that’s in A but not in nZ. Why? Because I want to end up writing A = nZ, heh heh. Let’s go.

Divide m by n — call the quotient q and the remainder r. We can write m = nq + r, right? So r = m − nq. But the condition on r (the natural one we mentioned earlier) is 0 ≤ r < n. And m can’t be 0, and m isn’t a multiple of n, so 0 < r < n.

Now, A is closed under subtraction, and m and nq are both in A, so r = m − nq is in A too, and BOOM — contradiction!!!!! I said n was the smallest positive element of A, but now this m hands us an r in A with 0 < r < n.

So ‘such an m’ — ‘an m in A but not in nZ’ — doesn’t exist. Which means A = nZ.

The conclusion: a nonempty subset of Z closed under +, −, × is ’the set of multiples of some n (nZ)’!!!

Congruences and factions

And one more concept tossed in!!! Let’s look at “congruences.” A congruence is what we’re talking about when we say “7 and 27 are congruent under ‘rule 5’.” That sentence, “7 and 27 are congruent under ‘rule 5’,” gets written as 7 ≡ 27 (mod 5). (Meaning 7 and 27 give the same remainder when divided by 5. Also catch that 27 − 7 is a multiple of 5.)

Then 30 ≡ 134 (mod 13) makes sense too. Right?! (Same here — catch that 134 − 30 is a multiple of 13. Kind of obvious when you think about it!!!! Riiight?)

Let me write it more generally. When we can write a ≡ b (mod n), we’re saying a − b is a multiple of n. Then “a − b is a multiple of n” means!!!! “a − b ∈ nZ.”

What properties does this ‘congruence relation’ have? (mod n)

• ① a ≡ a
• ② a ≡ b → b ≡ a
• ③ a ≡ b, b ≡ c → a ≡ c

Looking at these, they might seem obvious, but doesn’t this look like what we saw with matrices — the “similarity relation (similar)”?! Connecting it to that, we can say: “Integers form factions under ‘mod n’.”

Ex.) When mod n = 2: Z = {odd numbers} ∪ {even numbers} = {2Z + 1} ∪ {2Z} (in words: the set of elements with remainder 1 when divided by 2, plus the set with remainder 0).

Ex.) When mod n = 3: Z = {3Z} ∪ {3Z + 1} ∪ {3Z + 2} (in words: split into elements with remainder 0, 1, and 2 when divided by 3, written as sets).

Got it?!?! So when the factions split like this, we’re going to grab only a representative of each faction and form a set of representatives. (※Careful※: we’re representing the set this way — it’s not a set whose only elements are those representatives.)

For example, when n = 2 — I’m introducing the notation —

means this, and

we’ll write it like this. And didn’t I just say we’re defining the elements as the representatives?!

is what that means. The number 3 is, inside , the same as 1!! Because 1 and 3 are both “elements with remainder 1 when divided by 2,” right?

(※Careful again※: we’re representing the set this way — it’s not a set whose only elements are those representatives.) The reason I keep banging on about this caveat is that I’m worried you’ll mistake this for ’the set of natural numbers ≤ n.’

One more example…

(You might want to call it “the set of remainders when divided by 3,” but that’s not really an accurate description….. Try to wrap your head around it as best you can.)

OK now let’s check this. Is the set really closed under +, −, ×!!! i.e., is it free under +, −, ×. Since

we get

like that — yep, freely closed under +, −, ×.

(Hey. If a negative pops out it’s not in the set, so isn’t it inappropriate to say it’s closed under subtraction?! — if you ask that, it means you didn’t quite catch what I was saying. No wait. It means I didn’t explain it well enough….. For negatives, let me try this: under the setup above, isn’t −1 the same thing as n − 1 (just add n; in Z₂ that’s 1)? You can treat negatives as positives without worrying (in this context), so since it’s closed under +, it’s closed under − too.)

My explanation isn’t great.. Anyone who’s actually studied math (T_T)(T_T)(T_T) please save me!!!~~~~

Division and inverses

But why have I been asking, this whole time, only about closure under +, −, and ×? What about division?!

Because division is where I’m headed in the end. For these rings, if every nonzero element has a multiplicative inverse, we’ve got a field!!!! Division by zero is still off the table. Let’s get into it.

This kind of expression — we know it well, right? Here, in , the −1 is read “inverse,” and it means the ‘inverse element’ of b…. (inverse element: what the heck do you multiply by to get 1?!!!! The number that, multiplied with another, gives 1 — that’s the inverse of that number.) If some c, multiplied by b, gives 1, then c is the inverse of b~~~~.

Now let’s check whether an inverse exists in Z under the faction setup above, i.e., whether exists (the c whose product with b leaves remainder 1 when divided by n is the inverse of b).

Let’s just run through one example!!! The inverse of 2 in , i.e., does exist? Let’s see.

(Reflexively jumping to 1/2 — don’t, it doesn’t help here.)

Suppose 2 has an inverse, call it a: , i.e., . a is the number such that 2a, divided by 6, leaves remainder 1. i.e., 2a is “6 times something, plus 1,” so 2a = 6k + 1. Rearrange to 2a − 6k = 1. Left side is even. Right side is odd. Contradiction.

What is this… wrong?! Yes yes yes yes — in this case the inverse does NOT exist!!!!!

So does the “exists” case never happen?! No no no no no no, of course there are cases where it does. When it does!!!! There’s a “condition that has to be satisfied for the multiplicative inverse to always exist.”

If you want to find the inverse x of b, then in that case we can write , so must always be solvable.

aZ + bZ and the gcd

And there’s a certain proposition that helps a lot with solving this — easier to look at it through that lens.

Careful — this is NOT a union. That’s why we didn’t use ∪. What we want is ’the set of all numbers you get by picking one from each set and adding them’! Ahh, let me write it like this.

Hmm, then let’s check if this set is closed under addition…. Don’t even need to check. Obviously is.

Closed under multiplication too, obviously, right?! (Multiplication’s too obvious so I’ll skip it.)

So this thing is closed under +, −, × for starters, which means we can write it like this.

(A set closed under +, −, × is the set of multiples of some n~ — we proved that waaay up above.) (And that certain n is the gcd of a and b.)

The number n is the gcd of a and b. Right?!

Proof:

Both a and b end up being elements of nZ (just plug in x = 1, y = 0 for a and x = 0, y = 1 for b — easy), and a, b ∈ nZ means both a and b are multiples of n. Which means n is a divisor of a AND a divisor of b. (n is a common divisor of a and b.)

But why is it the greatest common divisor?

Suppose: there’s some divisor m of both a and b bigger than n, i.e., a common divisor m > n. For any number you pick from each set and add,

ax + by is always a multiple of m, and ax, by individually are multiples of m too. So — this equation makes no sense anymore. (It should say multiples of m.) It turns into — contradiction!!!! A common divisor m of a and b larger than n can’t exist!!!!

OK dokey. In aZ + bZ = nZ, n is the gcd of a and b. Here’s the notation:

gcd: greatest common divisor. cf) lcm: least common multiple

Special case: if gcd(a, b) = 1, then a and b are called ‘coprime.’ Translated to what we did above:

aZ + bZ = Z

∃ x, y ∈ Z s.t. ax + by = 1

OK back to the main thread. The condition for to always hold (i.e., for the multiplicative inverse to exist, so we’re closed under ÷) is that gcd(b, n) = 1.

So what condition makes that work for every nonzero class b in Zₙ? Easy — n is prime!!!! (Prime number: a whole number bigger than 1 that’s divisible only by 1 and itself.)

Inside this guy, +, −, ×, ÷ are all closed, so we can call it a field (Field)!!!

Example: when p = 37, let’s find the inverse of 15 inside .

Call the inverse x: , i.e., the number becomes 1 under the mod 37 rule, i.e., the remainder when divided by 37 has to be 1.

So such x & y always exist…..!!!!! Because gcd(15, 37) = 1!!!! The x here, i.e., the inverse of 15, is 5.

Conclusion: it’s not just the fields we already know — Q, R, C, sets closed under all four operations — there’s also out there!!!

Polynomials

Alright, let’s stop talking about integers and start talking about ‘polynomials.’ We’ve been dragging the integer thing on for aaaaages, haven’t we?!

Don’t worry about polynomials. By the time this post wraps up, everyone will have caught on: polynomials~ integers~ same difference.

OK let’s start. Earlier, when we wrote F[t], we meant

So why exactly are polynomials so similar to integers that I went on and on about integers and then leapt straight into polynomials?!

If , then f is a multiple of g, or g is a divisor of f!!!! — apparently… Whoa~~ Same concept as integers, that’s what they say.

Even better — f(t) ÷ g(t) can also be expressed as division ‘with a quotient and a remainder.’

(with the condition deg r < deg g) (q(t) and r(t) are uniquely determined.) Apparently you can write it like this!!!!!

This! This right here!!! The big deal is that this works not just for integers but also for polynomials.

The division-based facts we used — gcds, Bézout identities and sets of multiples — have polynomial versions too. The same quotient-and-remainder trick drives them!!!!

OK let me get more concrete. The multiples of f(t) can be expressed like this.

This is just notation, FYI~~ The actual thing I want to say is: if some subset A of F[t] is closed under +, −, and multiplication by any polynomial in F[t], then A “becomes the set of multiples of some polynomial!!!!!!!” (We proved exactly this kind of theorem when we did integers, remember? There, multiplying by any integer came free with adding over and over.)

Also, just like we had

we get

like this. Just as we split by the convention ‘mod n,’ grabbing only the representatives of each faction to make a set… the full polynomial set can be split into factions the same way, and that set, just like with integers, is not closed under ÷ in general.

BUT — when is it closed? With integers, splitting by the rule of prime numbers (prime number) gave us closure under division and we recognized it as a field (Field), remember?! In polynomials, what plays the role of a prime is “p(t): an irreducible polynomial.”

If the nonconstant polynomial p(t) is irreducible, the only way to write it as a product has a nonzero constant factor (so, essentially, p(t) = 1 · p(t)) — that’s what irreducible means!!!! (Just like an integer prime can’t be broken down further, an irreducible polynomial can’t be factored — that’s what it means.)

(Note) Whether something is irreducible can depend on the field (field)….. Like — over the real field, t² + 1 is irreducible, but over the complex field, no no no, not irreducible.

So, just as ended up closed under ÷ and became a field (field), is also closed under ÷ and is a field!!!

Something fun

Let me also throw in something fun. Look at !!!! If we write it that way, since it’s the set of remainders when divided by , the remainder is a polynomial of degree at most 1, so we can write = {a + bt}.

Checking +/− closure isn’t fun, so let’s look at multiplication. When a = 0, b = 1, a + bt becomes t, and t · t = t². Let’s see the remainder when we divide t² by t² + 1: can be written as , so dividing by gives a remainder of −1.

Huh?! Multiplying gives −1, and this is a “Field”?!

Wait — don’t we already know one such field (Field)?!

None other than the complex field, !!!!!!!!!!

In other words, , the field built this way, is, name aside, the same as the complex field C — swap t for i and you get a field that looks identical.

Apparently this is one way to define the complex number field.

End of polynomials^^ With all this background piled up, we’re heading toward the grand Decomposition Theorem!!!!

---

Heads-up. The figures here are the original notes, slips and all. A few things to watch for:

• In the definition of $a\mathbb{Z} + b\mathbb{Z}$, the set is $\{ax + by \mid x, y \in \mathbb{Z}\}$; the picture writes $ax + bx$.