Algebra Theorems

Question 1

mersenne composite numbers

Answer 1

let n∈ℕ. Suppose that n is composite. Then 2ⁿ -1 is composite

Question 2

infinite primes

Answer 2

There are infinitely many primes

Question 3

sequences containing no primes

Answer 3

let n∈ℕ. There exists a sequence of n consecutive natural numbers containing no primes.

Question 4

Factors of sums of integers

Answer 4

Let a,b,c∈ℤ. Suppose than a|b and a|c. Then a|(b+c).

Question 5

Factors of linear combinations of integers

Answer 5

Let a,b,c,k,l∈ℤ. Suppose that a|b and a|c. Then a|(kb+lc).

Question 6

Sequence of factors.

Answer 6

Let a,b,c∈ℤ. Suppose that a|b and b|c. Then a|c.

Question 7

Two numbers are factors of each other

Answer 7

Let a,b∈ℤ. Suppose that a|b and b|a. Then a = +-b

Question 8

division theorem

Answer 8

Let a∈ℤ and d∈ℕ. Then there exists unique q,r∈ℤ s.t. a=qd+r and 0<=r

Question 9

equal hcf of factor and remainder

Answer 9

Let a,b,q,r∈ℤ. Suppose that a=qb+r . Then, hcf(a,b) = hcf(b,r)

Question 10

Euclidean Algorithm verfication

Answer 10

Let a,b∈ℕ with a>b and let h be the output of Algorithm 2.12 (Euclidean algorithm). Then, h = hcf(a,b).

Question 11

Bezouts lemma

Answer 11

a,b∈ℤ and let h=hcf(a,b). Then there exists x,y∈ℤ s.t. h=xa +yb

Question 12

common factors of highest common factors

Answer 12

Let a,b,c∈ℤ and let h=hcf(a,b). Suppose that c is a common factors of a and b. The c|h.

Question 13

lcm multiplied by hcf

Answer 13

Let a,b∈ℕ. Then lcm(a,b).hcf(a,b)=ab

Question 14

divisibility of a multiple

Answer 14

Let a,b∈ℤ and p∈ℕ be prime. Suppose that p|ab. Then p|a or p|b

Question 15

divisibility of a multiple for r values

Answer 15

Let a₁,a₂,..,aₙ∈ℤ and p∈ℕ be prime. Suppose that p|a₁,a₂,..,aₙ. Then p|aᵢ for some i=1,2,..,n

Question 16

fundamental theorem of airthmetic

Answer 16

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

Question 17

what is √2

Answer 17

√2 is irrational

Question 18

imperfect squares are irrational

Answer 18

Let a∈ℕ. Suppose that a is not a perfect square, then √a is irational

Question 19

perfect nth powers of coprime products

Answer 19

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.

Question 20

same remainders

Answer 20

Let n∈ℕ and a,b∈ℤ. Then a≡bmodn iff a and b leave the same remainder when divided by n

Question 21

unique b

Answer 21

Let n∈ℕ and a∈ℤ. Then there exists unique b ∈ Z with 0 ≤ b < n such that a ≡ b mod n.

Question 22

properties of modulo

Answer 22

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)

Question 23

arithmetic operations on modulo

Answer 23

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

Question 24

multiple versions of az≡1modn

Answer 24

let n∈ℕ and a∈ℤ. Suppose that a is coprime to n. Then there exists z∈ℤ s.t. az≡1modn

Question 25

unique solutions to a linear congruence equation

Answer 25

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

Question 26

similar factors in linear congruence equations

Answer 26

Let n∈ℕ and a,b,c∈ℤ. Suppose that c is coprime to n and
ac ≡ bcmodn
Then,
a ≡ bmodn

Question 27

factors of multiples

Answer 27

Let a,b,c∈ℤ. Suppose that a is coprime to b and that a|c and b|c. Then ab|c.

Question 28

coprimes of multiples.

Answer 28

a,b,c∈ℤ. Suppose that a is coprime to c and that b is coprime to c. Then ab is coprime to c.

Question 29

Chinese remainder theorem

Answer 29

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ₖ