PRINT    

Divisibility Tests

By David A. Smith

This topic proves several divisibility tests and gives examples of each. Divisibility tests for 2, 3, 5, 7, 9, 11, and 13 are given. The divisibility tests for 7, 11, and 13 are nearly the same; and thus lead to a handy way of determining divisibility by 7, 11 and 13 simultaneously. The divisibility tests for powers of 2 and powers of 5 are also nearly the same. They both give a way to determine the highest power of solvability and thus are not recursive. The divisibility test for 3 and 9 are the standard tests that are known since childhood. All tests are represented with proofs.

Proposition (Divisibility Tests by Powers of 2) Let be the digits of a positive integer. Then is divisible by precisely when the integer made up of the last digits of is divisible by

    Proof. Since it follows for Therefore,













So, in particular,   or equivalently, for some integer   Thus, the highest power of that divides must divide the last digits of

Example (Divisibility Tests by Powers of 2) Determine the highest power of 2 that divides

    Solution. Since see that and But notice that Therefore, the highest power of 2 that divides is 6.

Proposition (Divisibility Tests by 3) Let be the digits of a positive integer. Then is divisible by 3 precisely when divisible by

    Proof. Since we have,



Therefore, and so is divisible by when is divisible by 3.

Example (Divisibility Tests by 3) Determine if 3 divides and

    Solution. Since



and 43 is not divisible by 3 neither is . Since,



and 24 is divisible by 3 so is .

Proposition (Divisibility Tests by Powers of 5) Let be the digits of a positive integer. Then is divisible by precisely when the integer made up of the last digits of is divisible by

    Proof. Since it follows for Therefore,













So, in particular,   or equivalently, for some integer Thus, the highest power of that divides must divide the last digits of

Example (Divisibility Tests by Powers of 5) Determine the highest power of 5 that divides

    Solution. Since see that and But notice that Therefore, the highest power of 5 that divides is 5.

Proposition (Divisibility Tests by 7) Let be the digits of a positive integer. Then is divisible by precisely when   divisible by

    Proof.  Since we have,







Therefore,

                (1)

and so is divisible by when the summation in (1) is divisible by 9.

Example (Divisibility Tests by 7) Determine if is divisible by 7.

    Solution. Since and we see that divides

Proposition (Divisibility by 9) Let be the digits of a positive integer. Then is divisible by 9 precisely when divisible by

    Proof. Since we have,  



Therefore, and so is divisible by when is divisible by 9.

Example (Divisibility Tests by 9) Determine if 9 divides and

    Solution. Since



and 34 is not divisible by 9 neither is . Since,



and 45 is divisible by 9 so is .

Proposition (Divisibility Tests by 11) Let be the digits of a positive integer.

(i) Then is divisible by 11 precisely when   divisible by

(ii) Then is divisible by precisely when   divisible by

    Proof.  (i) Since we have,  



Therefore, and so is divisible by when is divisible by 11.
    (ii) Since we have,  







Therefore,

                (2)

and so is divisible by when the summation in (2) is divisible by 11.   

Example (Divisibility Tests by 11) Determine if is divisible by 11.

    Solution. Since and we see that divides

Proposition (Divisibility Tests by 13)  Let be the digits of a positive integer. Then is divisible by precisely when   divisible by

    Proof.  Since we have,







Therefore,

                (3)

and so is divisible by when the summation in (3) is divisible by 13.

Example (Divisibility Tests by 13) Determine if is divisible by 13.

    Solution. Since and we see that divides

Number Theory Books