Divisibility in Z - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET PDF Download

Plan

1. Basics of divisibility
2. Prime numbers
3. Perfect numbers

Notations

Z- set of integers
P - set of positive integers (also Z⁺ , also N)
N- set of nonnegative integers (also N₀)
 logical AND
 logical OR
 (existential quantifier)
 exactly one (unique existential quantifier)
 (universal quantifier)
 integer part of x (or the floor function)

Basics of divisibility

In this chapter, we will discuss the divisibility of integers, the set of integers is denoted by Z. We will give a few detailed proofs of some of the basic facts about divisibility. Most of the properties are quite obvious, but it is still a good idea to know how to prove them.

Definition.

An integer b ≠ 0 divides another integer a iff  k ∈ Z that a  k . b.

We also say that b is a factor (or divisor) of a.

One frequently writes b | a to indicate that b divides a.

Exercise. Let a and b be positive integers ∈ Z⁺ and a >b. How many positive integers not exceeding a are divisible by b? In other words, find such c∈ Z⁺ that b < c < a and bc

Solution. All numbers divisible by b are in the form b * k , where k ∈ Z⁺. They are positive and do not exceed a,

Therefore, there are floor   such integers

Theorem 1. For all integers a, b, c ∈ Z

(1) 1  a,  -1  a and a  0.
(2) Reflexivity: a  a.
(3) Transitivity: a  b  b  c ⇒ a  c.
(4) Not-quite antisymmetry: a  b  b  a ⇒ a = b V a = -b.
(5) if a  ba  c ⇒ a  (n*m + m * c) for any integers n and m

Proof.

(1) and (2) follow immediately

and therefore x y = 1 (there are no zero-divisors in the integers). It follows that either y = x = 1 or y = x = -1. But x = 1 implies a = b, and x = -1 implies b = -a.

(5) Given b = x * a and c = y * a.

Consider n * b + m * c

nb + m c = x an +y am = a(xn+ ym)⇒ a(nb+ mc)

It follows

a  (n b + m c)

Application of Theorem 2.

Do there exist integers x, y, and z such that 6x
9 y
15z  107?

No, they don't, here is the proof by contradiction.

Since 3, 6 and 9 has a common divisor 3 than 3 must divide its linear combination 3  (6x + 9y +15z) = 3  107 which is wrong.

Question. How many divisors does a positive integer have?

Here is a picture of all divisors of integers in range [1, 500]

Primes

Observation. Every positive integer has at least two divisors: 1 and itself Definition. Integer p > 1 is called a prime if its only positive divisors are 1 and p.
Otherwise it is called a composite.

The number 1 is a special case which is considered neither prime nor composite

The number 2 is also special, it is the only even prime.

Theorem. There are an infinite number of primes

Proof. (by contradiction)

Assume otherwise, say, p₁ , …, p_n is a complete list of all primes.

Define

p = (p₁ * p₂ *...*p_n) +1.

Since this number p is larger than all the p_i , it cannot be prime.

But then, there is some prime that divides p. Since our list is supposedly complete that prime must be, say, pr .

We have that pr  p

But then p_r = 1.

A contradiction.
QED - end of proof ("quod erat demonstrandum").

How would you find (or generate) primes?
Sieve of Eratosthenes: (Greek astronomer, 195BC) 

Write down the integers from 2 to the highest number n you wish to include in the table. Cross out all numbers > 2 which are divisible by 2. Cross out all numbers >3 which are divisible by 3, then by 5 and so on. Continue until you have crossed out all numbers divisible by

Why do we stop at ?

Because the next number to cross must be n since we cross all numbers with divisors < 

Goldbach Conjecture (1742)

Prime numbers satisfy many strange and wonderful properties.

Observation:

6  3 + 3
7  5 + 2
8  5 + 3
9  7 + 2
10  7 + 3
18  11 + 7

What about 117 ? Can you represent it as sum of two primes?

Goldbach made the conjecture that every odd number > 5 is equal to the sum of three primes.

Euler replied that Goldbach's conjecture was equivalent to the statement that every even number > 2 is equal to the sum of two primes.

p₁ + p₂ + 2n

It is known to be true for for numbers through 6 *10¹⁶ (checked numerically in 2003)

Mersenne numbers

For some years, people believed that if p is prime, then so is 2^p -1:

2²-1, 2³ -1,2⁵ -1, ...

This is not true for all primes, for example

2¹¹ -1 = 2047  23 * 89

Mersenne Conjecture (15 century, by French monk Marin Mersenne) 2^p -1 is prime for p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 , 257 and composite for all other positive integers p < 257.

It took a few of centuries to show that the conjecture was wrong. Only in 1947 the range up to 258 was checked! It turned out that

a) 2⁶⁷ -1 and 2²⁵⁷ -1 are not primes
b) Mersenne missed p = 61, 89, 107.

Definition: When 2^p-1 is prime it is said to be a Mersenne prime.

The largest known Mersenne prime is (2005):

2^25,964,951  -1

Theorem. If 2^p -1 is prime, then p is prime.

Proof. By contradiction - we assume that 2^p-1 is prime, but p is not prime. Let p be a composite number, p  r *s. Consider the following polynomial

x^r*s - 1

It can be written as

which is easily proved by expanding the right hand side.
Therefore, if p is composite then x^p -1 is composite, so is 2^p-1, since it's divisible by 2^s -1.

Contradiction to our assumption that 2^p -1 is prime. QED.

Perfect numbers

Definition. An positive integer is a perfect number if it equals the sum of its proper divisors (not including itself).

The first few perfect numbers are

6 = 1 + 2 + 3
28 = 1 + 2 + 4 + 7 + 14
496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248
8128 = ...

Question. What is the next perfect number? It seems it should not be a problem to answer this by writing Java or C program.

Question. Are they all even?

This question is much much harder.... It is not known if any odd perfect numbers exist.

All even perfect number are in the form

6 = 1 + 2 + 3 = 2 * 3
28 = 1 + 2 + 3 + 4 + 5 + 6 +7 = 4 * 7
496 = 1 + 2 + 3 +... + 31 = 16 * 31
8128 = 1 + 2 + 3 +... + 127 = 64 * 127

Generally,

2^n-1(2ⁿ - 1), when n is prime

This is a relation between the perfect and the Mersenne primes. So the search for Mersenne primes is also the search for even perfect numbers!