Basic Divisibility Theorems.

Last Update xx.xx.2022

I was annoyed that there was not good online source with proofs about divisibility and specialy non-divisiblity. Showing that some natural number to natural number functions are not divisiable is hard in some extreame case when simple aritmetic playing does not work. Hence, this article's Theorems do not involve prime numbers, greatest common division, or lowest common multiple but simple $a ∣ b$ and $a ∤ b$ relationships.

Definition of divisibility is usually given only to natural numbers. However, definition used here also allows negative integers. Every Theorem starts with stating is variables used a natural number or integers to indentify is positivity reguired.

DEFINITION 0.0 (Divisibility)

\forall a, b \in Z (a ∣ b :\Leftrightarrow \exists α \in Z (α a = b))

DEFINITION 0.1 (Non-divisibility)

\forall a, b \in Z (a ∤ b :\Leftrightarrow \neg a ∣ b)

1. Starting notes on Divisibility

THEOREM 1.0 (Positive order)

(a, b \in N \land a ∣ b) \Rightarrow a \leq b

Let's say $α$ is the integer which $α a = b$ . Hence, $α = \frac{b}{a}$ . This means that $α$ to be an integer, $a \leq b$ . Otherwise, $α$ would be a non-integer rational number. Variable $a$ does not equal zero since division of zero is undefined and such cannot divade anything.

THEOREM 1.1 (One divades everthing)

\forall a \in Z (1 ∣ a)

Selecting $α = a$ , one gets $a 1 = a$ which proofs the divisibility of the claim.

THEOREM 1.2 (Integer divades itself)

\forall a \in Z (a ∣ a)

Selecting $α = 1$ , one gets $1 a = a$ which proofs the divisibility of the claim.

THEOREM 1.3 (Integer divading a sequence divades linear sum)

\forall a \in Z, {b_{i}} \in Z^{N}, {c_{i}} \in Z^{N}, \forall n \in N (\forall i \in N (a ∣ b_{i}) \Rightarrow a ∣ \sum_{i = 0}^{n} c_{i} b_{i})

Selectig

α = \sum_{i = 0}^{n} c_{i} α_{i}

where

α_{i}

are coefficients for

α_{i} a = b_{i}

, following is got:

\sum_{i = 0}^{n} (c_{i} α_{i}) a = \sum_{i = 0}^{n} (c_{i} α_{i} a) = \sum_{i = 0}^{n} (c_{i} b_{i}) .

This shows

a

divades

\sum_{i = 0}^{n} c_{i} b_{i}

THEOREM 1.4 (Integer divades an other iff coeffiecent time integer divades same coefficient times the other)

\forall a, b, c \in Z (a ∣ b \Leftrightarrow c a ∣ c b)

Having

α a = b

means

c b = c α a

which implies that

c a ∣ c b

with coeffient

α

. Having

α c a = c b

means

b = α a

. This implies

a ∣ b

with coefficient

α

THEOREM 1.5 (Modulus sum)

\forall a, x, x', y, y' \in Z ((a ∣ x - y \land a ∣ x' - y') \Rightarrow a ∣ (x + x') - (y + y'))

Sum of

x - y

and

x' - y'

x - y + x' - y' = (x + x') - (y + y')

. By Theorem 1.3 sum is divisiable by

a

therefore

(x + x') - (y + y')

is divisiable by

a

THEOREM 1.6 (Integer divading a other iff negative of integer divades the other)

\forall a, b \in Z (a ∣ b \Leftrightarrow - a ∣ b)

For

a \in Z

exits

α

such that

α a = b

which implies

(- α) (- a) = b

. Hence for

- a

exists

- α

. Since choice was for arbitary member of

Z

converse follows immeadly by

- (- a) = a

2. Starting notes on non-Divisibility

THEOREM 2.0 (Integer is non-divisiable with sum of a sequence implies a non-divisiable member in the sequence)

\forall a \in Z, {b_{i}} \in Z^{N}, n \in N (a ∤ \sum_{i = 0}^{n} (b_{i}) \Rightarrow \exists i' \in Z (a ∤ b_{i'}))

By Theorem 1.3 $\forall a \in Z, {b_{i}} \in Z^{N}, \forall n \in N (\forall i \in N (a ∣ b_{i}) \Rightarrow a ∣ \sum_{i = 0}^{n} b_{i})$ . This implies $\forall a \in Z, {b_{i}} \in Z^{N}, \forall n \in N (\neg a ∣ \sum_{i = 0}^{n} b_{i} \Rightarrow \neg \forall i \in N (a ∣ b_{i}))$ because $(χ \Rightarrow ψ) \Leftrightarrow (\neg ψ \Rightarrow \neg χ)$ . This leads to then $\forall a \in Z, {b_{i}} \in Z^{N}, n \in N (a ∤ \sum_{i = 0}^{n} (b_{i}) \Rightarrow \exists i' \in Z (a ∤ b_{i'}))$ .

3. Hybrid notes on both divisiable and non-divisiable

THEOREM 3.0 (Integer A divades an other integer means that A doesn't divade other integer plus value which absolute value is less than absolute value of A)

\forall a, b, r \in Z (((a ∣ b \land a ∤ r) \Rightarrow a ∤ (b + r)))

Since $b$ is divaded by $a$ then exists $α$ such that $b = α a$ . Hence $b α^{- 1} = a$ . Then $b + c = α a + c$

Bibliography:

Naoki Sato Notes