Nicodemi, O., Sutherland, M. and Towsley, G. (2007). An Introduction to Abstract Algebra. Upper Saddle River, NJ: Pearson Prentice Hall, pp.136-146, 150-163.

[3.5] The Fundamental Theorem of Algebra

The Fundamental Theorem of Algebra is:

Every non-constant Polynomial has a root in \(\mathbb{C}\), i.e.

\((\forall P(x) \in \mathbb{C}[x]: \deg{P(x) \geq 1), (\exists x \in \mathbb{C}: p(x)=0})\)

Proof

This is terribly complicated, have a look at p. 139 of TB.

Corollaries

From the Fundamental Theorem of Calculus factorisation properties can be deduced:

  1. Any Polynomial can always be expressed as product of complex linear factors

    • From Wk. 6 Material; a polynomial is a product of irreducible factors and,
    • By the Fundamental Theorem of Calculus, there must exist a root,
      • hence, it must be possible to write any complex polynomial as a product of linear factors

_

  1. Any polynomial can be expressed product of real linear or real quadratic factors

    • This follows from the first corollary because, essentially two complex linear factors can be multiplied to make a Real quadratic factor, and hence the polynomial would exist in the Real field of complex polynomials rather than the complex field.

Notes on this

  • These factorisation rules only apply to the fields of \(\mathbb{R}[x]\) and \(\mathbb{C}[x]\), nothing else.

  • While the factors do exist finding them can be really hard
    • As a matter of fact, the difficulty in finding prime factors of even numbers is the whole reason encryption works so well,
      • let alone finding the irreducible factors of a polynomial.

[3.7] Polynomial Congruences

Definition

let \(a(x), b(x), p(x)\) be polynomials in some field \(F[x]\),

then it is said that \(a(x)\) is congruent to \(b(x)\) if and only if \(p(x) | (a(x) - b(x))\):

\(a(x) \equiv b(x) \Longleftrightarrow p(x) | (a(x) - (b(x))\)

This also means that their remainders must be equivilant when divided by \(P(x)\)

Always exists a congruence solution

Say we have \(p(x)\) in some field \(F[x]\),

take some arbitrary \(a(x) \in F[x]\), by the division algorithm:

\(a(x) = p(x)\cdot q(x) + r(x), \hspace{1 cm} \exists \hspace{0.2 cm} p(x),q(x) \in F[x]\)

hence,

\(a(x) \equiv r(x) \pmod{p(x)}\)

Let \(r(x)=b(x)\)

\(a(x) \equiv b(x) \pmod{p(x)}\)

thus, every polynomial in a field must be congruent to some other polynomial of a lesser degree than \(p(x)\)

Lesser Degree

If \(a(x)\) and \(b(x)\) are of a lesser degree than \(p(x)\) then the only way than can be congruent modulo \(p(x)\) is if they are equal:

\[\begin{align} a(x) &\equiv b(x) \pmod{p(x)} \\ &\implies a(x) - b(x) = q(x) \cdot p(x) \hspace{1 cm} \exists \hspace{0.2 cm} q(x) \in F[x] \end{align}\]

but the left side is of a lesser degree than the right side and \(q(x)\) can only be a polynomial (i.e. it cant contain $), hence \(q(x) = 0\)

\[\begin{align} &\implies a(x) - b(x) = 0 \cdot p(x) \\ &\implies a(x) - b(x) = 0 \\ &\implies a(x) = b(x) \end{align}\]

thus, if \(a(x)\) and \(b(x)\) are of a lesser degree than \(p(x)\), the only way for them to be congruent modulo \(p(x)\) is if they are equal.

Congruence Classes

The congruence class of all solutions of \(a(x)\) modulo \(p(x)\) is the set of all values equivilant to \(a(x)\) modulo \(p(x)\) and is expressed as \([a(x)]_{p_(x)}\)

The Set of all Congruence Classes

Recall from the integers that a congruence class for \(3\) modulo \(7\) would be expressed as \([3]_7\), when dealing with polynomials we write \([a(x)]_{p(x)}\) which is more or less analagous.

Recall from the integers the set of all congruence classes modulo \(7\) would be expressed as \(\mathbb{Z}_7}\), well if these were polynomials we would write \(\mathbb{Z}\/<7>\)

Hence, the set of all congruence classes modulo \(p(x)\) is expressed as \(F[x]\/\langle p(x)\rangle\)

  • The set of all congruence classes modulo \(4x\) in the Real Field would be

    • \(\mathbb{R}[x]\/\langle 4x \rangle\)

    • How we might expect to see it written but not how it is expressed is
      • \(\mathbb{R[x]_{4x}}\)

Operations with Congruence Classes

These Congruence classes operate just like the once were used to dealing, that is, for some field \(F[x]\) and some \(p(x) \in F[x]\), addition and multiplication are commutative in \(F[x]\/\langle p(x)\rangle\)

LS0tDQp0aXRsZTogIkZ1bmRhbWVudGFsIFRoZW9yZW0gb2YgQWxnZWJyYSINCnN1YnRpdGxlOiAiV2VlayA3IE1hdGVyaWFsIg0Kb3V0cHV0OiANCiAgaHRtbF9ub3RlYm9vazogDQogICAgdGhlbWU6IGNvc21vDQotLS0NCg0KPHN1Yj48c3VwPiBOaWNvZGVtaSwgTy4sIFN1dGhlcmxhbmQsIE0uIGFuZCBUb3dzbGV5LCBHLiAoMjAwNykuICpBbiBJbnRyb2R1Y3Rpb24gdG8gQWJzdHJhY3QgQWxnZWJyYSouIFVwcGVyIFNhZGRsZSBSaXZlciwgTko6IFBlYXJzb24gUHJlbnRpY2UgSGFsbCwgcHAuMTM2LTE0NiwgMTUwLTE2My48L3N1cD48L3N1Yj4NCg0KDQojIyBbMy41XSBUaGUgRnVuZGFtZW50YWwgVGhlb3JlbSBvZiBBbGdlYnJhDQpUaGUgRnVuZGFtZW50YWwgVGhlb3JlbSBvZiBBbGdlYnJhIGlzOg0KDQo+RXZlcnkgbm9uLWNvbnN0YW50IFBvbHlub21pYWwgaGFzIGEgcm9vdCBpbiAkXG1hdGhiYntDfSQsIGkuZS4gIA0KPg0KPiAgIDxzdWI+JChcZm9yYWxsIFAoeCkgXGluIFxtYXRoYmJ7Q31beF06IFxkZWd7UCh4KSBcZ2VxIDEpLCAoXGV4aXN0cyB4IFxpbiBcbWF0aGJie0N9OiBwKHgpPTB9KSQ8L3N1Yj4gIA0KDQojIyBQcm9vZg0KVGhpcyBpcyB0ZXJyaWJseSBjb21wbGljYXRlZCwgaGF2ZSBhIGxvb2sgYXQgcC4gMTM5IG9mIFRCLg0KDQojIyBDb3JvbGxhcmllcw0KRnJvbSB0aGUgKkZ1bmRhbWVudGFsIFRoZW9yZW0gb2YgQ2FsY3VsdXMqIGZhY3RvcmlzYXRpb24gcHJvcGVydGllcyBjYW4gYmUgZGVkdWNlZDoNCg0KMS4gIEFueSBQb2x5bm9taWFsIGNhbiBhbHdheXMgYmUgZXhwcmVzc2VkIGFzIHByb2R1Y3Qgb2YgY29tcGxleCBsaW5lYXIgZmFjdG9ycyAgIA0KDQogICAgKiBGcm9tIFdrLiA2IE1hdGVyaWFsOyBhIHBvbHlub21pYWwgaXMgYSBwcm9kdWN0IG9mIGlycmVkdWNpYmxlIGZhY3RvcnMgYW5kLA0KICAgICogQnkgdGhlICpGdW5kYW1lbnRhbCBUaGVvcmVtIG9mIENhbGN1bHVzKiwgdGhlcmUgbXVzdCBleGlzdCBhIHJvb3QsDQogICAgICAgICogaGVuY2UsIGl0IG11c3QgYmUgcG9zc2libGUgdG8gd3JpdGUgYW55IGNvbXBsZXggcG9seW5vbWlhbCBhcyBhIHByb2R1Y3Qgb2YgbGluZWFyIGZhY3RvcnMgIA0KDQpfICAgDQoNCjIuICAgQW55IHBvbHlub21pYWwgY2FuIGJlIGV4cHJlc3NlZCBwcm9kdWN0IG9mIHJlYWwgbGluZWFyIG9yIHJlYWwgcXVhZHJhdGljIGZhY3RvcnMgIA0KDQogICAgICAqIFRoaXMgZm9sbG93cyBmcm9tIHRoZSBmaXJzdCAqY29yb2xsYXJ5KiBiZWNhdXNlLCBlc3NlbnRpYWxseSB0d28gY29tcGxleCBsaW5lYXIgZmFjdG9ycyBjYW4gYmUgbXVsdGlwbGllZCB0byBtYWtlIGEgUmVhbCBxdWFkcmF0aWMgZmFjdG9yLCBhbmQgaGVuY2UgdGhlIHBvbHlub21pYWwgd291bGQgZXhpc3QgaW4gdGhlIFJlYWwgZmllbGQgb2YgY29tcGxleCBwb2x5bm9taWFscyByYXRoZXIgdGhhbiB0aGUgY29tcGxleCBmaWVsZC4NCg0KIyMjIE5vdGVzIG9uIHRoaXMNCiogVGhlc2UgZmFjdG9yaXNhdGlvbiBydWxlcyBvbmx5IGFwcGx5IHRvIHRoZSBmaWVsZHMgb2YgJFxtYXRoYmJ7Un1beF0kIGFuZCAkXG1hdGhiYntDfVt4XSQsIG5vdGhpbmcgZWxzZS4NCg0KKiBXaGlsZSB0aGUgZmFjdG9ycyBkbyBleGlzdCBmaW5kaW5nIHRoZW0gY2FuIGJlIHJlYWxseSBoYXJkDQogICogQXMgYSBtYXR0ZXIgb2YgZmFjdCwgdGhlIGRpZmZpY3VsdHkgaW4gZmluZGluZyBwcmltZSBmYWN0b3JzIG9mIGV2ZW4gbnVtYmVycyBpcyB0aGUgd2hvbGUgcmVhc29uIGVuY3J5cHRpb24gd29ya3Mgc28gd2VsbCwNCiAgICAqIGxldCBhbG9uZSBmaW5kaW5nIHRoZSBpcnJlZHVjaWJsZSBmYWN0b3JzIG9mIGEgcG9seW5vbWlhbC4NCiAgICANCiAgICANCiAgICANCiMjIFszLjddIFBvbHlub21pYWwgQ29uZ3J1ZW5jZXMNCg0KIyMjIERlZmluaXRpb24NCg0KbGV0ICRhKHgpLCBiKHgpLCBwKHgpJCBiZSBwb2x5bm9taWFscyBpbiBzb21lIGZpZWxkICRGW3hdJCwNCg0KPnRoZW4gaXQgaXMgc2FpZCB0aGF0ICRhKHgpJCBpcyBjb25ncnVlbnQgdG8gJGIoeCkkIGlmIGFuZCBvbmx5IGlmICRwKHgpIHwgKGEoeCkgLSBiKHgpKSQ6DQo+DQo+PHN1Yj4kYSh4KSBcZXF1aXYgYih4KSBcTG9uZ2xlZnRyaWdodGFycm93IHAoeCkgfCAoYSh4KSAtIChiKHgpKSQgPC9zdWI+DQoNCg0KDQpUaGlzIGFsc28gbWVhbnMgdGhhdCB0aGVpciByZW1haW5kZXJzIG11c3QgYmUgZXF1aXZpbGFudCB3aGVuIGRpdmlkZWQgYnkgJFAoeCkkDQoNCiMjIyBBbHdheXMgZXhpc3RzIGEgY29uZ3J1ZW5jZSBzb2x1dGlvbg0KDQpTYXkgd2UgaGF2ZSAkcCh4KSQgaW4gc29tZSBmaWVsZCAkRlt4XSQsDQoNCnRha2Ugc29tZSBhcmJpdHJhcnkgJGEoeCkgXGluIEZbeF0kLCBieSB0aGUgZGl2aXNpb24gYWxnb3JpdGhtOg0KDQokYSh4KSA9IHAoeClcY2RvdCBxKHgpICsgcih4KSwgXGhzcGFjZXsxIGNtfSAgIFxleGlzdHMgXGhzcGFjZXswLjIgY219IHAoeCkscSh4KSBcaW4gRlt4XSQNCg0KaGVuY2UsDQoNCiRhKHgpIFxlcXVpdiByKHgpIFxwbW9ke3AoeCl9JA0KDQpMZXQgJHIoeCk9Yih4KSQNCg0KJGEoeCkgXGVxdWl2IGIoeCkgXHBtb2R7cCh4KX0kDQoNCg0KdGh1cywgZXZlcnkgcG9seW5vbWlhbCBpbiBhIGZpZWxkIG11c3QgYmUgY29uZ3J1ZW50IHRvIHNvbWUgb3RoZXIgcG9seW5vbWlhbCBvZiBhIGxlc3NlciBkZWdyZWUgdGhhbiAkcCh4KSQNCg0KIyMjIyBMZXNzZXIgRGVncmVlDQoNCklmICRhKHgpJCBhbmQgJGIoeCkkIGFyZSBvZiBhIGxlc3NlciBkZWdyZWUgdGhhbiAkcCh4KSQgdGhlbiB0aGUgb25seSB3YXkgdGhhbiBjYW4gYmUgY29uZ3J1ZW50IG1vZHVsbyAkcCh4KSQgaXMgaWYgdGhleSBhcmUgZXF1YWw6DQoNClxiZWdpbnthbGlnbn0NCg0KYSh4KSAmXGVxdWl2IGIoeCkgXHBtb2R7cCh4KX0gXFwNCiAgICAgICZcaW1wbGllcyBhKHgpIC0gYih4KSA9IHEoeCkgXGNkb3QgcCh4KSBcaHNwYWNlezEgY219IFxleGlzdHMgXGhzcGFjZXswLjIgY219IHEoeCkgXGluIEZbeF0NCg0KXGVuZHthbGlnbn0NCg0KYnV0IHRoZSBsZWZ0IHNpZGUgaXMgb2YgYSBsZXNzZXIgZGVncmVlIHRoYW4gdGhlIHJpZ2h0IHNpZGUgYW5kICRxKHgpJCBjYW4gb25seSBiZSBhIHBvbHlub21pYWwgKGkuZS4gaXQgY2FudCBjb250YWluICRcZnJhY3sxfXt4fSksIGhlbmNlICRxKHgpID0gMCQNCg0KXGJlZ2lue2FsaWdufQ0KDQogICAgICAmXGltcGxpZXMgYSh4KSAtIGIoeCkgPSAwIFxjZG90IHAoeCkgIFxcDQogICAgICAmXGltcGxpZXMgYSh4KSAtIGIoeCkgPSAwICBcXA0KICAgICAgJlxpbXBsaWVzIGEoeCkgICA9IGIoeCkgIA0KDQpcZW5ke2FsaWdufQ0KDQp0aHVzLCBpZiAkYSh4KSQgYW5kICRiKHgpJCBhcmUgb2YgYSBsZXNzZXIgZGVncmVlIHRoYW4gJHAoeCkkLCB0aGUgb25seSB3YXkgZm9yIHRoZW0gdG8gYmUgY29uZ3J1ZW50IG1vZHVsbyAkcCh4KSQgaXMgaWYgdGhleSBhcmUgZXF1YWwuDQoNCiMjIENvbmdydWVuY2UgQ2xhc3Nlcw0KDQpUaGUgY29uZ3J1ZW5jZSBjbGFzcyBvZiBhbGwgc29sdXRpb25zIG9mICRhKHgpJCBtb2R1bG8gJHAoeCkkIGlzIHRoZSBzZXQgb2YgYWxsIHZhbHVlcyBlcXVpdmlsYW50IHRvICRhKHgpJCBtb2R1bG8gJHAoeCkkIGFuZCBpcyBleHByZXNzZWQgYXMgJFthKHgpXV97cF8oeCl9JA0KDQojIyMgVGhlIFNldCBvZiBhbGwgQ29uZ3J1ZW5jZSBDbGFzc2VzDQoNClJlY2FsbCBmcm9tIHRoZSBpbnRlZ2VycyB0aGF0IGEgY29uZ3J1ZW5jZSBjbGFzcyBmb3IgJDMkIG1vZHVsbyAkNyQgd291bGQgYmUgZXhwcmVzc2VkIGFzICRbM11fNyQsIHdoZW4gZGVhbGluZyB3aXRoIHBvbHlub21pYWxzIHdlIHdyaXRlICRbYSh4KV1fe3AoeCl9JCB3aGljaCBpcyBtb3JlIG9yIGxlc3MgYW5hbGFnb3VzLg0KDQpSZWNhbGwgZnJvbSB0aGUgaW50ZWdlcnMgdGhlIHNldCBvZiBhbGwgY29uZ3J1ZW5jZSBjbGFzc2VzIG1vZHVsbyAkNyQgd291bGQgYmUgZXhwcmVzc2VkIGFzICRcbWF0aGJie1p9Xzd9JCwgd2VsbCBpZiB0aGVzZSB3ZXJlIHBvbHlub21pYWxzIHdlIHdvdWxkIHdyaXRlICRcbWF0aGJie1p9XC88Nz4kDQoNCkhlbmNlLCB0aGUgc2V0IG9mIGFsbCBjb25ncnVlbmNlIGNsYXNzZXMgbW9kdWxvICRwKHgpJCBpcyBleHByZXNzZWQgYXMgJEZbeF1cL1xsYW5nbGUgcCh4KVxyYW5nbGUkDQoNCiAgKiBUaGUgc2V0IG9mIGFsbCBjb25ncnVlbmNlIGNsYXNzZXMgbW9kdWxvICQ0eCQgaW4gdGhlIFJlYWwgRmllbGQgd291bGQgYmUNCiAgDQogICAgICogJFxtYXRoYmJ7Un1beF1cL1xsYW5nbGUgNHggXHJhbmdsZSQNCiAgICAgDQogICAgICogSG93IHdlIG1pZ2h0IGV4cGVjdCB0byBzZWUgaXQgd3JpdHRlbiBidXQgbm90IGhvdyBpdCBpcyBleHByZXNzZWQgaXMNCiAgICAgICAgKiB+JFxtYXRoYmJ7Ult4XV97NHh9fSR+DQogICAgICAgIA0KIyMjIyBPcGVyYXRpb25zIHdpdGggQ29uZ3J1ZW5jZSBDbGFzc2VzDQoNClRoZXNlIENvbmdydWVuY2UgY2xhc3NlcyBvcGVyYXRlIGp1c3QgbGlrZSB0aGUgb25jZSB3ZXJlIHVzZWQgdG8gZGVhbGluZywgdGhhdCBpcywgZm9yIHNvbWUgZmllbGQgJEZbeF0kIGFuZCBzb21lICRwKHgpIFxpbiBGW3hdJCwgYWRkaXRpb24gYW5kIG11bHRpcGxpY2F0aW9uIGFyZSBjb21tdXRhdGl2ZSBpbiAkRlt4XVwvXGxhbmdsZSBwKHgpXHJhbmdsZSQ=