Algebra

Least common multiple🔗

The LCM is called a MGN (minsta gemensamma nämnare) in Swedish because it's for use in a denominator. You have several fractions with different denominators and want to expand them to use the same. In principle it doesn't have to be about denominators, so call it LCM.

To find the LCM of two numbers, construct a number that contains all the prime factors of both.

Bigger than the Greatest common factor (GCF), in the sense that you use every prime you have access to (though not in their full multiplicity). Note the naming of LCM versus GCF. "Multiple" refers to a product of possibly many numbers, "factor" refers to something you can factor out of a single number.

Greatest common factor🔗

To find the GCF of two numbers, find what primes they share.

Use Divisibility tests or the Euclidean algorithm.

Smaller than the Least common multiple (LCM) in a sense, that you don't use all the primes you have access to. In reality it's apples and oranges. The LCM is to expand two fractions to have the same denominator, so that you can then add them. The GCF is to deexpand a single ratio (fraction or equation) to its most simplified form.

In short, you shrink a denominator to the GCF, or you expand a denominator to the LCM.

Triangle inequality🔗

See Anki cards. Basically |x| + |y| ≥ |xy|, because x and y, being vectors or complex numbers, take a long way around while xy takes the shortest way.

Triangle inequality for integrals (PB 294)

Modular arithmetic

The rules are braindead. This wand just works everywhere.

(A)^B mod C ≡ (A mod C)^B mod C

(A + B) mod C ≡ A mod C + B mod C

(A * B) mod C ≡ A mod C * B mod C

Division algorithm🔗

You've used long division. You're familiar with getting a quotient and a remainder? This is just a realization of that, which we can then use for other things. Warning: the polynomial q(x) has an unfortunate name, it is not the quotient. Without further ado, realize that:

for two polynomials p(x) and q(x), there are unique polynomials r and k such that

$\frac{p(x)}{q(x)} = k(x) + \frac{r(x)}{q(x)}$

which can be written

$\frac{p(x)}{q(x)} = \frac{q(x)k(x)}{q(x)} + \frac{r(x)}{q(x)}$

which is the same as

$p(x) = q(x)k(x) + r(x)$

See the Polynomial Remainder Theorem on how to use this last form.

Polynomial Remainder Theorem🔗

Divide the polynomial p(x) with (x - a). The remainder will be identical to the value of plugging a into the original: p(a). This lets us know all sorts of things. If the remainder is zero, then (x - a) did divide the polynomial cleanly, and a is a root.

Restate the original Division algorithm, $p(x) = q(x)k(x) + r(x)$

in these terms. New division algorithm: $p(x) = (x - a)k(x) + p(a)$

Which leaves only k(x) as the unknown.

Example

Suppose a polynomial p(x). Someone divides it with (x-1)(x-2)(x-6). What's the remainder, if p(1)=2, p(2)=1, p(6)=-4?

Wow, I have no idea….

The first step is to see how you can fit this into the division algorithm. The divisor is q(x), so:

$p(x) = q(x)k(x) + r(x)$ $\iff p(x) = (x-1)(x-2)(x-6)k(x) + r(x)$

Now, the remainder r(x) must have a degree less than 3, because by definition, writing p(x)/q(x) as k(x) + r(x)/q(x), means r(x) has a lower degree than q(x). It doesn't matter what degree p(x) and k(x) are, the "leftover" gets shunted into k. I think.

So r(x) can be written as a second-degree expression, so our equation is: $p(x) = (x-1)(x-2)(x-6)k(x) + ax^2 + bx + c$

Moving on. Let's gather some facts. The exercise supplies us the remainder for three different values of x. We will insert those values into the expression for r(x).

$\begin{align*} p(1) = 2 &= a(1)^2 + b(1) + c \\ p(2) = 1 &= a(2)^2 + b(2) + c \\ p(6) = -4 &= a(6)^2 + b(6) + c \end{align*}$

You recognize what to do with this: it's a system of equations.

1	1	1	2
4	2	1	1
36	6	1	-4

1	1	1	2
36	6	1	-4
0	-2	-3	-7

1	1	1	2
0	-30	-35	-76
0	-2	-3	-7

1	1	1	2
0	-2	-3	-7
0	0	10	29

1	1	1	2
0	-2	-3	-7
0	0	1	29/10

Simplified third row

1	1	1	2
0	-2	0	17/10
0	0	1	29/10

1	0	1	57/20
0	-2	0	17/10
0	0	1	29/10

1	0	0	-1/20
0	-2	0	17/10
0	0	1	29/10

1	0	0	-1/20
0	1	0	-17/20
0	0	1	29/10

Simplified second row

So we found values for a, b, and c. We're done: the remainder r(x) is $-\frac{x^2}{20} - \frac{17x}{20} + \frac{58}{20}$ .

ANSWER NOT VERIFIED

Example 2

What's the remainder when you divide x⁸⁶ - 3x⁷ + 6 by (x² - 1)?

Try the Polynomial Remainder Theorem. Test the cases where x is 1 or negative 1, because this makes the divisor zero.

Plugging the data into the division algorithm, We have x⁸⁶ - 3x⁷ + 6 = (x² - 1)k(x) + r(x).

p(1) = 1 - 3 + 6 = 4
p(-1) = 1 - -3 + 6 = 10

At p(1) and p(-1), the RHS just becomes r(x). So we know that at x=1, not only that the remainder r(x) is 4, but that the whole polynomial evaluates to 4. Remember that we are dividing by a specific divisor in this exercise, so we better not pick some willy-nilly x when we analyze the remainder.

The remainder r(x) will be at most degree one, see other example. So we'll write it as ax + b.

For x=1, we have a(1) + b = 4 For x=-1, we have a(-1) + b = 10

We can find a and b, and thereafter, we'll be able to write the remainder.

Key trick: Pick an x that makes the divisor zero.

Euclidean algorithm🔗

Let's find GCF(209,77). Realize that 209 can be restated in units of 77, plus something to make up the remainder.

209 = (2 * 77) + 55

This rewrite is the basic step. Repeat: restate 77 in terms of the new thing.

77 = (1 * 55) + 22
55 = (2 * 22) + 11
22 = (2 * 11) + 0

The algorithm is: Re-apply division until you get zero remainder. Then the divisor you just tried is the GCF.

Diophantine equation

Diophantine equations come in many forms. Fermat's Last Theorem is a famous example. What we mean with this word, 'Diophantine', is that we're interested in integer solutions only. This is why it has applications for e.g. proving the Fundamental Theorem of Arithmetic, which is about prime numbers, which of course are integers. We're going to solve a simple kind, the linear Diophantine equation.

Note: it may seem pointless to run the Euclidean algorithm when you can detect that two numbers share no common factor. But you do it for the steps in the process, not the end result (that GCF=1).

Take an equation of the form ax + by = c, where a, b, and c are known integers, and we're interested in integer solutions. For example 43x + 19y = 4.

Normally equations of this form describe a continuous line, crossing an infinite number of points in the real plane, and some such equations even manage to skip any integer pair (x, y).

Crux: For there to be an integer solution to ax + by = c, then all GCF(a,b) must be a factor of c. If a and b have a common factor not shared by c, then stop. There are no integer solutions. This means you can't e.g. have even numbers for both a and b and an odd number for c, but one of a or b may be even, and c may be too.

Aside: a statement (ka + lb) is a linear combination of (a + b). Therefore, ax + by is a linear combination, too. You can put in any x and y. Anything that divides (a + b) will retain its ability to divide (ax + by).

EXAMPLE: My seminarieuppgift

Bestäm den lösning till den diofantiska ekvationen $123x+35y=5004$ , som har minst positiva x-värde.

Jag verifierar att $\textrm{SGD}(123,35)$ är 1.

Vi skriver en hjälpekvation och får partikulärlösning $x=2$ , $y=-7$ , vilket multiplicerat med $5004$ kan stoppas in i ursprungsekvationen.

Då återstår att bestämma den allmänna lösningen till en lite annorlunda ekvation (en generell): $ax + by = 0$ där $\textrm{SGD}(a,b) = 1$ , vilket säger att $a$ och $b$ inte delar varandra. Ekvationen kan skrivas $ax = -by$ . Om a inte delar $b$ måste det dela $y$ , eller hur? Förklaring: pga likhetstecknet (vi struntar i minus) måste precis samma faktorer ingå i $ax$ som i $by$ , eftersom de är samma tal. Så givet att $a$ inte har faktorerna i $b$ , så måste $a$ ha faktorer i $y$ (inte nödvändigtvis alla, men $y$ innehåller alla faktorer till $a$ , vilket kan uttryckas med bokstaven $k$ för ''resten av faktorerna/de som inte ingår i $a$ '' så att $y = ka$ ).

Vi har att $y$ kan uttryckas $ka$ , så vi byter $y$ mot $ka$ i ekvationen och med algebra får att $x = -kb$ .

Vi tittar på den specifika ekvationen (ytterligare en ny ekvation för oss) $123x + 35y = 0$ . Vi har nu lösningar till den eftersom $a$ och $b$ är definierade. Lösningarna var som sagt $x = -kb$ och $y = ka$ , så till den specifika ekvationen är det $x = -35k$ och $y = 123k$ .

Dessa är ingen speciell lösning utan en allmän, där $k$ är något heltal. Nu applicerar vi detta till ursprungsekvationen, vilken hade partikulärlösningarna $x=2(5004)$ och $y=-7(5004)$ , vilket kan ses som vårt ''offset'' från origo. Ta dessa, plus eller minus $(-35, 123)$ något antal ( $k$ ) gånger, så rör vi oss längs linjen som utgör ekvationen. Varje steg är en till heltalslösning: de ligger $(-35, 123)$ ifrån varandra.

Vilken är den heltalslösning med minst positiva x-värde? Vi skriver en formel för x: $2(5004) - 35k$ . Vi sätter $k$ till $285$ vilket ger ett x-värde på $33$ . För samma $k$ blir y-värdet $27$ .

\begin{svar*} Den lösning med minst positiva x-värde är $(33, 27)$. \end{svar*}

Fundamental Theorem of Arithmetic🔗

All numbers are either primes, or a combination of primes.

Fundamental Theorem of Algebra

Minimally stated: Every positive-degree polynomial has a complex zero.

Alternatively: An nth-degree polynomial has n zeros, if you include complex zeros and count multiplicity (duplicate zeros).

That follows from the minimal statement, because once you know you have a zero, you can factor it out and are left with a new (lower-degree) polynomial, which of course also has a zero.

Divisibility tests🔗

Divisible by 2 if it's even.
Divisible by 3 if the sum of the digits are.
Divisible by 5 if it ends in zero or five.
- An odd number containing the factor five will end in five.
- An even number containing the factor five will end in zero.

Divisibility by three

Intuition for divisibility by three can be helped by that 1000 can be rewritten (1 + 999), 100 as (1 + 99), etc. The nine-rich terms leave no remainder after division and can hence be deleted.

400 can be written 4(1+99), meaning 4 + 4*99, and the latter term can be deleted as any multiple of 99 will keep on being divisible by 3. What remains is the value of the hundredth-place digit, in this case… four.

Convert the number 462 yourself: 4 + (4*99) + 6 + (6*9) + 2. After deleting the parenthesed terms, you are left with… the digits in the original number!

99 is also divisible by 9, so the same test can be used for divisibility by 9.

Set theory

domain and range

take a function f: A → B
- the domain is A, can refer to it by D_f
- the målmängd is B
  - the range (värdemängd) V_f is a subset of B

find the range of a function

see if it has a min or max

The range of a function that only takes on the values 1 and 2 is written {1,2}, not [1,2], which would be the full interval.

Interval

A closed interval [a,b] includes the ends. $\{x \in \mathbb R | a \le x \le b\}$ .

[a,b]  --------[a----------b]--------

An open interval ]a,b[ excludes the ends. Unfortunate notation. $\{x \in \mathbb R | a < x < b\}$ .

]a,b[  ---------a[--------]b---------

Sum/difference of cubes🔗

Memory key: the sum will have a binomial factor that contains a plus sign, just like the sum itself.

a³ + b³ = (a + b)( … )

a³ - b³ = (a - b)( … )

Complete formula

a³ + b³ = (a + b)(a² − ab + b²)

a³ - b³ = (a − b)(a² + ab + b²)

Inequality

Well-ordering principle

Complex binomial

Solve x³ − 125i = 0 for $\mathbb C$ .

Complex quadratic

Transcendental numbers

First, the notion of algebraic numbers: a number that can be a solution to some equation with rational coefficients. This would be most numbers that you actually use.

One example is √2 because it is the solution to x² - 2 = 0. It is algebraic.

Though there are many more transcendental numbers than algebraic, it is hard to prove that a number isn't algebraic. Examples of proven transcendentals include π and e.

What links here

Math

Created 2016-Nov-17 (7 years ago)