Algebra Theorems Flashcards
mersenne composite numbers
let n∈ℕ. Suppose that n is composite. Then 2ⁿ -1 is composite
infinite primes
There are infinitely many primes
sequences containing no primes
let n∈ℕ. There exists a sequence of n consecutive natural numbers containing no primes.
Factors of sums of integers
Let a,b,c∈ℤ. Suppose than a|b and a|c. Then a|(b+c).
Factors of linear combinations of integers
Let a,b,c,k,l∈ℤ. Suppose that a|b and a|c. Then a|(kb+lc).
Sequence of factors.
Let a,b,c∈ℤ. Suppose that a|b and b|c. Then a|c.
Two numbers are factors of each other
Let a,b∈ℤ. Suppose that a|b and b|a. Then a = +-b
division theorem
Let a∈ℤ and d∈ℕ. Then there exists unique q,r∈ℤ s.t. a=qd+r and 0<=r
equal hcf of factor and remainder
Let a,b,q,r∈ℤ. Suppose that a=qb+r . Then, hcf(a,b) = hcf(b,r)
Euclidean Algorithm verfication
Let a,b∈ℕ with a>b and let h be the output of Algorithm 2.12 (Euclidean algorithm). Then, h = hcf(a,b).
Bezouts lemma
a,b∈ℤ and let h=hcf(a,b). Then there exists x,y∈ℤ s.t. h=xa +yb
common factors of highest common factors
Let a,b,c∈ℤ and let h=hcf(a,b). Suppose that c is a common factors of a and b. The c|h.
lcm multiplied by hcf
Let a,b∈ℕ. Then lcm(a,b).hcf(a,b)=ab
divisibility of a multiple
Let a,b∈ℤ and p∈ℕ be prime. Suppose that p|ab. Then p|a or p|b
divisibility of a multiple for r values
Let a₁,a₂,..,aₙ∈ℤ and p∈ℕ be prime. Suppose that p|a₁,a₂,..,aₙ. Then p|aᵢ for some i=1,2,..,n
fundamental theorem of airthmetic
let n∈ℕ with n>1. Then:
a) there exists prime numbers p₁≤ p₂≤ …≤ pₖ such that n=p₁p₂…pₖ
b) if q₁≤q₂≤…≤pₗ are prime numbers such that n=q₁q₂..qₗ, then k=l and qᵢ=pᵢ for all i=1,2,..,k
what is √2
√2 is irrational
imperfect squares are irrational
Let a∈ℕ. Suppose that a is not a perfect square, then √a is irational
perfect nth powers of coprime products
Let a,b,n∈ℕ suppose a is coprime to b, and ab is a perfect nth power. Then both a and b are perfect nth powers.
same remainders
Let n∈ℕ and a,b∈ℤ. Then a≡bmodn iff a and b leave the same remainder when divided by n
unique b
Let n∈ℕ and a∈ℤ. Then there exists unique b ∈ Z with 0 ≤ b < n such that a ≡ b mod n.
properties of modulo
Let n∈ℕ and a,b,c∈ℤ Then:
(a) a ≡ a mod n; (Reflexive property)
(b) if a ≡ b mod n, then b ≡ a mod n; and (Symmetric property)
(c) if a ≡ b mod n and b ≡ c mod n, then a ≡ c mod n. (Transitive property)
arithmetic operations on modulo
Let n,m∈ℕ and a,b,a₀,b₀∈ℤ. Suppose that a ≡ b mod n and that
a) a+a’ ≡ (b+b’)modn
b) aa’ ≡bb’modn
c) aᵐ=bᵐmodn
multiple versions of az≡1modn
let n∈ℕ and a∈ℤ. Suppose that a is coprime to n. Then there exists z∈ℤ s.t. az≡1modn
unique solutions to a linear congruence equation
let n∈ℕ and a,b∈ℤ. Suppose that a is coprime to n. Consider the linear congruence equation
ax ≡ bmodn
Then there exists s∈ℤ s.t. the solutions of A are given by x≡smodn
similar factors in linear congruence equations
Let n∈ℕ and a,b,c∈ℤ. Suppose that c is coprime to n and
ac ≡ bcmodn
Then,
a ≡ bmodn
factors of multiples
Let a,b,c∈ℤ. Suppose that a is coprime to b and that a|c and b|c. Then ab|c.
coprimes of multiples.
a,b,c∈ℤ. Suppose that a is coprime to c and that b is coprime to c. Then ab is coprime to c.
Chinese remainder theorem
Let n₁,n₂,..,nₖ∈ℕ and a₁,a₂,…,aₖ∈ℤ. Suppose that hcf(nᵢ,nⱼ)=1 for i≠j. Consider the system of simultaneous congruences
x≡a₁modn₁
x≡a₂modn₂
…
x≡aₖmodnₖ
Then there exists s∈ℤ s.t. the solution of the systemgiven by x≡smodn₁.n₂..nₖ
