Divisibility

For an integer m and a nonzero integer n, we say that m is divisible by n or n divides m if there is an integer k such that m = kn;

We denote this by n | m

If m is divisible by n, then m is called a multiple of n; and n is called a divisor (or factor) of m.

Because 0 = 0 · n, it follows that n | 0 for all integers n.

For a fixed integer n, the multiples of n are 0,±n,±,2n,....

If m is not divisible by n, then we write n
m

(a) x | x (reflexivity property);
 (b) If x | y and y | z, then x | z (transitivity property);
 (c) If x | y and y =/= 0, then |x|≤|y|;
(d) If x | y and x | z, then x | αy+βz for any integers α and β;
(e) If x | y and x | y ±z, then x|z;
(f) If x | y and y | x, then |x|=|y|;
(g) If x | y and y=/=0, then x/y |y;
(h) for z=/=0, x | y if and only if xz | yz.

Division Algorithm

For any positive integers, a and b there exists a unique pair (q, r ) of nonnegative integers such that b = aq +r and r < a. We say that q is the quotient and r the remainder when b is divided by a.

(1) Inthiscase,weassumethata>b.Wecansetq=0andr=b<a;that is, (q,r) = (0,b).


(2) Suppose that a = b. We can set q = 1 and r = 0 < a; that is, (q,r) = (1, 0).

(3) Finally, assume that a < b. There exist positive integers n such that na > b. Let q be the least positive integer for which (q + 1)a > b. Then qa ≤ b. Let r = b − aq. It follows that b = aq + r and 0 ≤ r < a.

Divisibilidad

Un número ｎ es divisible por ｐ si existe un 𝑘 natural tal que:

ｎ | ｐ⟺ ｎ＝𝑘p ，𝑘∈ℕ₊

ｎ en base ｂ
ｎ＝∑ｂⁱ𝒂ᵢ
ｎ | ｐ⟺
∑ 𝒂ᵢ 𝑟ᵢ ≡ 0 modₚ
𝑟ᵢ≔ ｂⁱ/ｐ

Ejemplo

255|3 :
    2∙100 + 5∙10 + 5∙1
    𝑟ᵢ={100/3;10/3;1/3}
        ={33.3͝;3.3͝;0.3͝}
∑ 𝒂ᵢ 𝑟ᵢ ≡ 0 mod₃
        = 2∙33.3͝ + 5∙3.3͝ + 5∙0.3͝
        = 66.6͝ + 16.6͝ + 1.6͝
        = 70+13+1.9͝= 83+2 = 85
        = 25*3 ≡ 0 mod₃ 
        ∎𝘊𝘘𝘋

Greater Common Divisor

Euler Algorithm

function GCD(𝑎,𝑏) is
   begin
   if 𝑏=𝟶 return 𝑎;
   else return GCD(𝑏, 𝑎 mod 𝑏);
   end; 

Divisivilidad de números

de 2

n is divisible(2)
   if n mod 10 is divisible(2)
   -- Last digit is 2,4,6,8,0

de 3

n is divisible(3)
   if sum_of_digits(n) is divisible(3)
   -- Digits sums to 3,6,9

de 5

n is divisible(5)
   if n mod 10 is divisible(5)
   -- Last digit is 5,0

de 9

n is divisible(9)
   if sum_of_digits(n) is divisible(9)
   -- Digits sums to 9

de 10

n is divisible(10)
   if n mod 10 is 0
   -- Last digit is 0