Divisibility Proof

Prove or disprove. Let \(a,b,\) and \(d\) be integers with \(d\neq0\). If \(d\mid a\) and \(d\mid b\), then \(d^2\mid ab\).

Proof

Assume \(d\in\mathbb{Z}\setminus\{0\}\).

If \(d\mid a\) and \(d\mid b\), then, there exists \(q,r\in\mathbb{Z}\) such that \(dq=a,dr=b\).

Then, \(ab=(dq)(dr)=d^2(qr)\).

Since \(qr\in\mathbb{Z},d^2(qr)=ab\Leftrightarrow d^2\mid ab\).

Thus, \(d^2\mid ab\).

■ (Q.E.D)

Section 2: Unique Factorization

• Dudley, Underwood. Elementary Number Theory. 2nd ed. New York: W.H. Freeman and Company, 1989.

• Prime Number
  an integer that is greater than 1 and has no positive divisors other than 1 and itself
• Composite Number
  an integer that is greater than 1 but is not prime

Example 1: Prime Numbers

Example 1. How many even primes are there? How many whose last digit is 5?

What is an even number greater than 1? An even number follows \(n=2k,k\in\mathbb{N}\).

What is an odd number greater than 1? An odd number follows \(n=2k+1,k\in\mathbb{N}\).

[part 1] Solution- How many even primes are there?

Since a prime number is defined to be an integer greater than 1, the first prime number is 2, and then all even numbers greater than 2 are always divisible by 2, thus making 2 the only even prime number.

Answer- There is 1 even prime number.

[part 2] Solution- How many whose last digit is 5?

The first prime number ending with 5, is 5. Then, we see that all numbers with the last digit of 5, are divisible by 5 so there is only one prime number with the last digit of 5.

Let \(n=10k+5\) be any number with the last digit of 0. Then \(n+5\) will have a last digit of 5. Since \(n+5\) has a last digit of 5, \(5\mid10k+5\) iff there exists a \(d\in\mathbb{N}\) such that \(5d=10k+5\). It is clear the \(n\) is divisible by 5, and hence 5 is the only prime with the last digit of 5.