Number Theory and Polynomial Background for the Decomposition Theorem [Linear Algebra I Studied #19]

OK so what’s a natural number….. First off, the set of naturals gets written like

but Naver’s 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 integer-only thing —

I’m going to write division like this. There’s a property hiding in here.

100 ÷ 17 = 5 ····· 8

When you express division like this — what do you call it, “elementary school division” (?) lol lol lol — when you write it that way:

let me put it in general terms.

Writing a = bq + r, the property in Z is that q and r are unique (with the condition 0 ≤ r < b).

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 ⊂ Z and A is closed under +, −, ×, can we claim A has the form nZ~~~?!?!?!

Answer: YES!!!!

Here’s why. Let n be the smallest positive element inside A.

Didn’t I say A is closed under addition????

Then n + n = 2n ∈ A, and 3n ∈ A.

And so on — without even checking, every multiple of n is in there!! heh heh heh

So we can write ’nZ ⊂ A’!!! Nice!~

For now, A might be a bit bigger than nZ?!?!

So suppose there’s some m that’s in A but not in nZ.

I want to show A = nZ, heh heh heh 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.

Since A is closed under addition, from m = nq + r we get nq ∈ A and r ∈ A,

and BOOM — contradiction!!!!!

I said n was the smallest positive element of A,

but now apparently there’s some m inside A producing an r 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 set closed under +, −, × can always be described as ’the set of multiples of some n (nZ)’!!!!!

And one more concept tossed in!!! Let’s look at “congruences.”

A congruence is what we mean when we say “7 and 27 are congruent under ‘rule 5’,”

and that means: “7 and 27 are congruent under mod 5” → 7 ≡ 27 (mod 5),

written like this.

(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!!!! Yeah, obvious.)

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,

(※Heads up※: 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?

(※Heads up 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

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

closed under +, −, ×!!!

i.e., is it free under +, −, ×.

Since

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, −1 and 1 are the same, right?

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!!!!!!!!!!!!!!!!!!~~~~

But why have I been asking,

this whole time, only about closure under +, −, and ×?

What about division?!?!!!!!!!!!!!!!

Because division is the whole point.

If we can also get closure under ÷, then that set qualifies as a ‘field (Field)’!!!!

Let’s get into it.

This kind of expression — we know it well, right?

Here,

the −1 is read “inverse,”

and it means the ‘inverse element’ of b…. (inverse element: what the heck do you multiply b 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 as defined above.

i.e., does

exist (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:

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.

For when it exists!!!!

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

must always be solvable.

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

Heads up — 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 +, −, ×.

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=0, y=0 — 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., suppose there’s 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 any further

this equation makes no sense. (It should be a multiple of m.)

Like this — contradiction!!!!

A common divisor m of a and b larger than n can’t exist!!!!

OK cool.

In aZ + bZ = nZ, n is the gcd of a and b.

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 this to always hold (i.e., for the multiplicative inverse to always exist, i.e., for ÷-closure)

is that gcd(b, n) = 1.

So what condition makes that work for every b? Easy — n is prime!!!!

(Prime number: a number divisible only by 1 and itself.)

Inside this guy, +, −, ×, ÷ are all closed,

so we can call it a field (Field)!!!!!!!!!!!!!!!!!!!!

Example:

When p = 37,

inside

let’s find the inverse of 15.

Call the inverse x.

i.e.,

x is the number that, under mod 37, becomes 1,

i.e., the remainder when divided by 37 is 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!!!!!

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, you’ll all probably notice — like I think you’ll catch — that polynomials and~ integers~ are basically the same thing.

OK let’s start.

We said earlier that if we write F[t],

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

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.)

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.

Because every proposition we proved with integers came from the fact that division-with-quotient-and-remainder works — that was the foundation everything else stretched out from,

which means every property we saw with integers carries over to polynomials!!!!

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 +, −, ×, then A “becomes the set of multiples of some polynomial!!!!!!!”

(We proved exactly this kind of theorem when we did integers, remember?)

Also,

just like we had

and split it using 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 ÷,

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 p(t) is irreducible, the only way to write it as a product is 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