Abstract Algebra Term

Bezouts

For any integers a and b, d = gcd(a, b) is the smallest positive integer that can be written as a linear combination of a and b: $d = sa + tb \quad \text{for some } s, t \in \mathbb{Z}$

$$\gcd(a,b)$$

$$=\prod p_{i}^{\min(a_{i},b_{i})}$$

$$\text{lcm}(a,b)=$$

$$\prod p_{i}^{\max(a_{i},b_{i})}$$

Rotman's Proposition 1.53

$$\gcd(a, b) \cdot \text{lcm}(a, b) = a \cdot b$$

Euclid's Lemma

If p is a prime and p|ab, then p|a OR p|b

Dirichlet's Theorem

The linear sequence an + b contains infinitely many primes if and only if gcd(a, b) = 1.

Frobenius

If gcd(a, b) = 1, the largest integer that cannot be written as ax + by is $\text{Frob}(a,b)=ab-\left(a+b\right)$

Freshman's Dream

$$(a+b)^{p}\equiv a^{p}+b^{p}(\bmod p)$$

Chinese Remainder Theorem

If gcd(m1, m2) = 1, the simultaneous system: $x \equiv b_1 \pmod{m_1} \quad \text{and} \quad x \equiv b_2 \pmod{m_2}$ has a solution (mod m1*m2)

Euler's Totient Function

phi(p) = p - 1 and phi(p^a) = p^a - p^(a-1)

Euler's Theorem

If gcd(a, n) = 1, then: $a^{\phi(n)} \equiv 1 \pmod n$

Fermat's Theorem

a^p = a (mod p) AND a^{p-1}= 1 (mod p) if p doesn’t |a