ΘρϵηΠατπ

Divides
an integer n is divisible by another integer m if there exists an integer k such that n=k⋅m. If this is all true we write m|n.
Divisible iff Integer Quotient
Suppose that a|b iff ba∈ℤ
Suppose that a|b, then there is some k∈ℤ such that a⋅k=b therefore k=ba, and since k∈ℤ then ba∈ℤ as needed.
n Factorial is Divisible by Its Factors
For any k∈[1,…,n] k|n!
n!=1⋯k⋯n therefore n!k=1⋯(kk)⋯n∈ℤ so therefore k|n!
Not Divisible iff Non-Integer Quotient
a∤b iff ba∉ℤ
By the fact that P⟺Q iff ¬P⟺¬Q
1 Divides Everything
Suppose that j∈ℤ, then 1|j
In the definition of divides take k=j, then we can see that j=j⋅1 thus we can say that 1|j
If something Divides One then it is One or Negative One
Suppose d|1 then d=±1
We have that 1=kd but the only numbers in ℤ that have a multiplicative inverse are 1,−1 so d must be one of those or else we have a contradiction.
If Zero Divides a Number, then that Number is Zero
Suppose 0|d then d=0
By definition we have d=k⋅0=0 so d=0
0 is Divisible by Everything
for any d∈ℤ,d|0
In the definition of divides take k=0, then we can see that 0=0⋅d thus we can say that d|0
Everything Divides Itself
Let a∈ℤ then a|a
Clearly 1⋅a=a therefore a|a
Division is Transitive
Suppose a|b and b|c then a|c
We have that b=kaa and c=kbb therefore c=kb(kaa) therefore by taking kc=(kakb) we see that a|c
If you Divide a Number, then You Divide their Multiples
For any a,b,c∈ℤ a|b⟹a|bc
Suppose that a|b therefore there is k∈ℤ such that b=ka, therefore multiply both sides to get bc=(kc)a and therefore a|bc as needed.
If it Divides it's Less than or Equal with Absolute Values
Suppose that n,d∈ℤ, such that n≠0 then if d divides n, then |d|≤|n|

We see that n=kd for some k∈ℤ, since n≠0 then also we must have k,d≠0 specifically note that |k|≥1 so that we have |n|=|kd|=|k|⋅|d|≥1|d|=|d| so that |n|≥|d|

We have to specify n≠0 because we know that everything divides zero, and therefore without that assumption we could use it to claim that since −42|0 that |−42|≤0 which is clearly false.

Larger Absolute value Implies no Division
for any n,d∈ℤ such that n≠0 if |d|>|n| then d∤n
This follows by the contrapositive and this
If two Numbers Divide each other then Their Absolute Values are Equal
For any a,b∈ℤ, if a|b and b|a then |a|=|b|

If a=0 then because a|b then this forces b=0 so that a=b=0, also if we assumed b=0 the same thing occurs.

In the case that neither of a,b=0 then recall that if a|b we have |a|≤|b| also since b|a then also |a|≤|b| so that |a|=|b|.

If a Number Divides another Then Given a Common Factor Their Quotients Divide Each Other
Suppose that a,b,d∈ℕ1 such that a|b and that d is a common divisor of a,b, then ad|bd
Divisibility is a Partial Order on the Natural Numbers
Divisibility is a partial order on ℕ0.
It is reflexive because we know that everything divides itself, we know it is transitive, and we also know that it is anti-symmetric, because for any n∈ℕ0,|n|=n and using this proposition.

Note that we can't quite get a partial order ℤ because of the fact that −a|a.

Linearity of Division
Suppose that a|b1,…,bn then a|c1b1+⋯+cnbn where a,bi,ci∈ℤ

For the base case of n=2 if a|b1 and a|b2 then we know that there are k1,k2∈ℤ such that b1=k1a and b2=k2a so that c1b1+c2b2=c1(k1a)+c2(k2a)=a(c1k1+c2k2).

For the induction step, assume the statement holds true for k∈ℕ1 and we'll show that it holds true for k+1 so suppose that a|b1,…bk+1 by the induction hypothesis we know that a|c1b1+⋯+ckbk so we get some j′∈ℤ such that c1b1+⋯+ckbk=j′a and also some j′′∈ℤ such that bk+1=j′′a and therefore c1b1+⋯+ckbk+ck+1bk+1=j′a+j′′a=a(j′+j′′) so therefore a|c1b1+⋯+ck+1bk+1

Even Number
We say that an integer n∈ℤ is even if there is some k∈ℤ such that n=2k
A power of an Even Number is Even
If n∈ℤ is even, then for any m∈ℕ1 we have nm is even
If n is even then there is some k∈ℤ such that n=2k and therefore nm=(2k)m=2mkm=2(2m−1km) so that nm is also even.
Odd Number
We say that an integer n∈ℤ is odd if there is some k∈ℤ such that n=2k+1
A power of an Even Number is Odd
If n∈ℤ is odd, then for any m∈ℕ0 we have nm is odd

Base case, set m=0 then nm=1 which is odd. For the induction step assume it holds true for k∈ℕ0 so that nk is odd, which means that there is some j∈ℤ such that nk=2j+1 therefore nk+1=(2j+1)n but n is odd so there is some j′∈ℤ such that n=2j′+1 and thus nk+1=(2j+1)(2j′+1)=4jj′+2j+2j′+1=2(2jj′+j+j′)+1 hence nk+1 is prime so the statement follows from the principle of induction.

Product of Two Equal Factors means They are Square Roots
Suppose that a=bc then b=a iff b=c

⟹ suppose that b=a then for sake of contradiction if b≠c then if c<b then we see that a=bc<bb=aa=a which is impossible, on the other hand if c>b=a then we see a=bc<cc<aa which yields the same contradiciton.

⟸ Now suppose that b=c therefore a=bc=bb therefore b2=a and so b=a as needed, moreover in this case note that c=a as well.

Product Implies Square Root bound on Factors
Suppose that a,b,c∈ℕ1 and that b≠c where a=bc then (b>a∧c<a)∨(b<a∧c>a)
Suppose for the sake of contradiction that it was not true, so that we knew that (b≤a∨c≥a)∧(b≥a∨c≤a) Suppose that b≤a and b≥a holds true, then b=a since c≠b then if c<b we see that bc<aa=a which is a contradiction since we know that bc=a, if it turns out that c≤a and c≥a it is handeled symetrically.

On the other hand if we know that b≤a and that c≤a, since b≠a then we know that b≠a, therefore more specifically we see that b<a this implies that a=bc<aa=a which is a contradiction. In the case of c≥a and b≥a it follows in a symmetrical manner.

Number To the Power m Minus 1 Divides Number To the Power n if m Divides n
Let a,m,n∈ℕ1 then m|n⟹(am−1)|(an−1)

We have that n=mk for some k∈ℤ and we want to prove that amk−1=(am−1)j for some j∈ℤ, a good guess would be that j=a(m−1)k which produces (am−1)(a(m−1)k)=amk−a(m−1)k and so we have to get rid of the a(m−1)k term, which inspires us to try j=a(m−1)k+a(m−2)k which yields (am−1)(a(m−1)k+a(m−2)k)=akm+a(m−1)k−(a(m−1)k+a(m−2)k)=akm−a(m−2)k

As we've just run into the same problem as last time we see that adding a(m−3)k would remove the most recent residue term, but then leave the new residue term a(m−3)k . Therefore formally using induction we can show that (am−1)(∑i=0m−1aik)=amk−1=an−1 where 1 is really the residue term a(0)k