Forward to §1.3 | Back to §1.1 | Up | Table of Contents | About this document

**Definition 1.2.1.**
The nonzero integers a and b are said to be
**relatively prime**
if (a,b) = 1.

**Proposition 1.2.2.**
Let a,b be nonzero integers.
Then (a,b) = 1 if and only if there exist integers m,n such that

ma + nb = 1 .

**Proposition 1.2.3.**
Let a,b,c be integers.

**(a)**If b | ac, then b | (a,b)c.**(b)**If b | ac and (a,b) = 1, then b | c.**(c)**If b | a, c | a and (b,c) = 1, then bc | a.**(d)**(a,bc) = 1 if and only if (a,b) = 1 and (a,c) = 1 .

**Definition 1.2.4.**
An integer p > 1 is called a
**prime number**
if its only divisors are ± 1 and ± p.
An integer a > 1 is called
**composite**
if it is not prime.

**Lemma 1.2.5. [Euclid]**
An integer p > 1 is prime if and only if it satisfies the following property:
If p | ab for integers a and b, then either p | a or p | b.

**Theorem 1.2.6. [Fundamental Theorem of Arithmetic]**
Any integer a > 1 can be factored uniquely
as a product of prime numbers, in the form

a =
p_{1}^{m1}
p_{2}^{m2}
** · · ·**
p_{n}^{mn}

**Theorem 1.2.7. [Euclid]**
There exist infinitely many prime numbers.

**Definition 1.2.8.**
A positive integer m is called the
**least common multiple**
of the nonzero integers a and b if

**(i)**m is a multiple of both a and b, and**(ii)**any multiple of both a and b is also a multiple of m.

**Proposition 1.2.9.**
Let a and b be positive integers with prime factorizations

a =
p_{1}^{a1}
p_{2}^{a2}
** · · · **
p_{n}^{an}
and b =
p_{1}^{b1}
p_{2}^{b2}
** · · · **
p_{n}^{bn} ,

For each i let d

**(a)**gcd(a,b) = p_{1}^{d1}p_{2}^{d2}**· · ·**p_{n}^{dn}**(b)**lcm[a,b] = p_{1}^{m1}p_{2}^{m2}**· · ·**p_{n}^{mn}

Since the fundamental theorem of arithmetic (Theorem 1.2.6) is proved in this section, you now have some more familiar techniques to use, involving factorization into primes.

**23.**
(a) Use the Euclidean algorithm
to find gcd (1776,1492).

(b) Use the prime factorizations of 1492 and 1776
to find gcd (1776,1492).
*Solution*

**24.**
(a) Use the Euclidean algorithm
to find gcd (1274,1089).

(b) Use the prime factorizations of 1274 and 1089
to find gcd (1274,1089).
*Solution*

**25.**
Give the lattice diagram
of all divisors of 250.
Do the same for 484.
*Solution*

**26.**
Find all integer solutions of the equation xy + 2y - 3x = 25.
*Solution*

**27.**
For positive integers a,b, prove that
gcd (a,b) = 1 if and only if
gcd(a^{2},b^{2}) = 1.
*Solution*

**28.**
Prove that n - 1 and 2n - 1 are relatively prime,
for all integers n > 1.

Is the same true for 2n - 1 and 3n - 1?
*Solution*

**29.**
Let m and n be positive integers.
Prove that

gcd (2^{m} - 1, 2^{n} - 1) = 1
if and only if gcd (m,n) = 1.
*Solution*

**30.**
Prove that gcd (2n^{2} + 4n - 3, 2n^{2} + 6n - 4) = 1,
for all integers n > 1.
*Solution*

Solutions to the problems | Forward to §1.3 | Back to §1.1 | Up | Table of Contents