Math 455.1  •  9 March 2009

Divisibility

Version 7.01

Copyright © 2009 by Murray Eisenberg.  All rights reserved.

Integers

The built-in Mathematica function IntegerQ tests whether its argument is an integer. Get brief information about IntegerQ:

?IntegerQ

Try these examples:

IntegerQ[5]
IntegerQ[-14]

And try these examples:

{ IntegerQ[-14/4],IntegerQ[-14/7],IntegerQ[(Sqrt[3])],IntegerQ[((((Sqrt[2])))^2)] }

There ought to be a shorter way of doing that same thing.  Let's try the following:

IntegerQ[{-14/4,-14/7,(Sqrt[3]),((((Sqrt[2])))^2)}]

Of course that's the correct answer.  After all, the list {-14/4,-14/7,(Sqrt[3]),((((Sqrt[2])))^2)} is not itself an integer. But there is a shorter way of checking the "integerness" of each of the elements of a list all at once—by mapping the function IntegerQ onto the list. Like this:

Map[IntegerQ,{-14/4,-14/7,(Sqrt[3]),((((Sqrt[2])))^2)}]

An expression of the form Map[func, lis] evaluates the function func in turn at each of the entries in the list lis and assembles the results back into a list. A shortcut—an abbreviation, really—for the preceding is:

IntegerQ/@{-14/4,-14/7,(Sqrt[3]),((((Sqrt[2])))^2)}

Why remember one more thing—this shortcut notation? Well, it often makes it easier to type and to read a longer expression by avoiding the brackets […] that would otherwise be needed to enclosing the arguments to Map.

Suppose you want to make a table that lists a bunch of numbers and, for each, indicates whether or not it is an integer. You may do so like this:

nums={-14/4,-14/7,(Sqrt[3]),((((Sqrt[2])))^2)};
Transpose[{nums,IntegerQ/@nums}]//TableForm

How does one cook up such a thing?   Step-by-step, like this:

nums={-14/4,-14/7,(Sqrt[3]),((((Sqrt[2])))^2)};

IntegerQ/@nums

{nums,IntegerQ/@nums}

So far we have a potential two-row table, with the first row giving the original numbers and the second row telling whether or not each is an integer.  We can even view it in table form:

{nums,IntegerQ/@nums}//TableForm

The two rows there should be columns, and the columns should be the rows.  To interchange rows and columns, use Transpose:

Transpose[{nums,IntegerQ/@nums}]

Finally, use TableForm to display this 4-row, 2-column table in the usual way:

Transpose[{nums,IntegerQ/@nums}]//TableForm

And we may put headings on the table, too:

TableForm[Transpose[{nums,IntegerQ/@nums}],TableHeadings->{None,{"number","integer?"}}]

The Division Theorem

The fundamental result is the following:

For example, take a = 14 and b = 5. Then
	14 = 2 × 5 + 3	and	0 ≤ 2 < 5 ,
so that
	14  div 5 = 2	and	 14  mod 5 = 3.

What does the Division Theorem say when a = 15 and b = 5? What are 15  div 5 and 15  mod 5?
What does the Division Theorem say when a = 16 and b = 7? What are 16  div 5 and 15  mod 5?

The Division Theorem merely asserts the existence and uniqueness of the quotient q and the remainder r. It does not provide a procedure for finding the quotient q and the remainder r. Of course you know such a procedure for finding q and r by hand calculation: "long division".

Try this: Use long division (by hand, without a calculator or Mathematica) to find 2009  div 455 and 2009  mod 455.

To find the remainder using Mathematica, use the built-in function Mod. To get some quick information about Mod, evaluate the next cell.

?Mod

Try these examples:

Mod[14,5]

Mod[15,5]

Mod[16,7]

To find the remainders of several numbers for the same divisor, use a list of integers as the first argument to Mod:

Mod[{14,15,16},5]

A quick way to form a list of consecutive integers is by using the built-in function Range. For example:

Range[2,7]

Divisors and the user-defined function dividesQ

The word "divisor" was used above in connection with the Division Theorem to describe the given integer b in the form a = q b + r. But the same word is also used in another, more special way: when the remainder r = 0.

For example, 6 divides 24, but 5 does not divide 24. That is, 6 ∣ 24, but 5 ∤ 24.Try this: By hand computation (without calculator or Mathematica) find all the positive integers that divide 24.

Strictly speaking divisors could be negative, too. For example, -6 divides 24. We will seldom have use for negative divisors, however. So usually when we refer to divisors of an integer, we shall mean only positive divisors.

To tell whether one integer divides another, you may use Mod.

Mod[24,6]==0
Mod[24,5]==0

Mathematica already has a built-in function to test whether one integer divides another: Divisible.  For example:

{Divisible[24,6], Divisible[24,5], Divisible[24,1]}

It seems reasonable that you should be able to test a whole bunch of potential divisors at once. Indeed, Divisible can do this:

Divisible[24,{6,5,1}]

And, for a given potential divisor, Divisible can work with an entire list of potential dividends:

Divisible[{24,20,25},5]

Further, Divisible can work with both a list of potential divisors and a list of potential dividenes:

Divisible[{24,20,25},{6,5,1}]

What will happen if you try lists of different lengths as the arguments, for example, a list of 3 potential dividends but only 2 potential divisors? Try it to find out!

To say that the built-in function Divisible automatically extends to entire lists, as in the preceding examples, is to say that it has the "attribute" of being Listable. Question: How can you tell that Divisible is, in fact, Listable—aside from checking examples such as above?  Answer: Ask to see all the attributes of this function:

Attributes[Divisible]

Even though Mathematica already has the built-in function Divisible, it's instructive to define your own function to do test whether one integer divides another. Here's one way—evaluate the next cell before proceeding.

dividesQ[d_, n_] := IntegerQ[d] && IntegerQ[n] && Mod[n, d] == 0

In the preceding definition, the doubled ampersand symbol && means "and". Thus dividesQ[d, n] is true exactly when both d and n are integers and the remainder on dividing d into n is 0.

Try these examples:

{dividesQ[6, 24], dividesQ[5, 24], dividesQ[1, 24]}

Notice that dividesQ uses arguments in the reverse order from the way that the built-in Divisible uses them. That is, dividesQ[d,n] means the same thing as Divisible[n,d].

What happens if you try a list for one of the arguments to dividesQ?

dividesQ[{6, 5,1}, 24]

Surprised? The difficulty here is the same as with IntegerQ. Like IntegerQ, but unlike Divides, our function dividesQ does not automatically work the way you might expect with list arguments.

[Perhaps you think you should be able to Map the function dividesQ onto the list {6, 5, 0}, just as you mapped IntegerQ onto a list earlier. However, things are more complicated with dividesQ than with IntegerQ: whereas IntegerQ takes only one argument, dividesQ takes two. (For a way to deal with this directly by mapping, see the Appendix, below.)]

To make dividesQ work nicely with list arguments, we explicitly give it the Listable attribute. Be sure to evaluate the next cell before proceeding.

SetAttributes[dividesQ, Listable]

Now try again what was unsuccessful before:

dividesQ[{6, 5,1}, 24]

It just so happens that Mathematica already has a built-in function, Divisors, for finding all the positive divisors of an integer.

For the next exercise you will need a way to add up a list of numbers without explicitly inserting plus signs between consecutive members of the list.  The form Apply[Plus, nums] does what's needed:

Apply[Plus, {1, 2, 4}]

Apply[Plus, {1, 2, 3}]

Don't confuse Apply with Map.  One good way to understand the difference is to look at the animations for these functions on the Animated Mathematica Functions web page.  (Click the preceding hyperlink!)

There's a shortcut for Apply you might want to use: instead of the form Apply[func, lis] you may use the abbreviation func@@lis. Try it:

Plus@@{1,2,3}

Note that @@ is the shortcut for Apply, whereas /@ is the shortcut for Map.  As with the shortut for Map, the reason for the shortcut is to make expressions, well, shorter— and so easier to type and to read.

A more direct way to add up a list is to use the built-in function Total:

Total[ {1, 2, 4}]

Nonetheless, it is still worthwhile to understand the Apply[Plus[lis]] form, since the same thing works more generally, with other functions than Plus.

Appendix: pure functions with mapping (optional)

Suppose we want to double a number (or several numbers). Easy: multiply the number (or list of numbers) by 2.

2 {5, 7, 9}

Suppose, next, we want to define a function that doubles a number.  Again, easy:

double[x_]:=2x

double[5]

And since multiplication is automatically a "listable" function, that function we define also automatically works upon whole lists without any further work:

double[{5,7,9}]

Suppose, next, we want to use a doubling function "anonymously"—without actually giving it a name.  (Why do that? Hold on for a while!) To do it, use the Mathematica function Function, like this:

Function[x,x^2] [5]

Function[x,x^2][{5,7,9}]

The x in Function[x, x^2] is a "dummy variable", just like the x in a definite integeral such as (∫_0^π)(e^(-2 x)) cos(x)dx.  So that letter may be replaced by another, for example:

Function[t,t^2] [5]

The first argument to Function tells Mathematica what the dummy variable is. Rather than use any actual letter as the dummy variable in a Function[var, body] expression, there's a shortcut: in the second argument body, use the symbol # in place of the dummy variable, get rid of everything else there, and follow the whole thing with an ampersand &. In our example, (#^2)& means exactly the same thing as Function[x,x^2].  Thus:

(#^2)& [5]

(#^2)& [{5,7,9}]

An expression having the form body& is called a pure function.

One of the places where pure functions are handy is when you start with a function of two (or more) variables—for example, the function dividesQ defined earlier—and you want to fix one of its arguments to be some constant value, thereby obtaining a function of its other variable(s) only. Let's do that here, but start the definition all over again.

goesIntoQ[d_,n_]:=IntegerQ[d]&&IntegerQ[n]&&Mod[n,d]==0

{goesIntoQ[6,24],goesIntoQ[5,24]}

Suppose now we want to test a whole list of numbers to see if the "go into" 24. This means that in the form goesIntoQ[d,n] the second argument should be fixed as the constant 24 whereas the first argument should still be variable.  A pure function to the rescue:

goesIntoQ[#,24]&[6]

And now you can map that pure function onto a whole list:

goesIntoQ[#,24]&/@{6,5,1}

If you wish, you may even give a name to the pure function goesIntoQ[#, 24] &.

goesInto24Q=goesIntoQ[#,24]&

(Mathematica actually regards the # as being #1. And yes, you can have a pure function of several variables, which would be designated by #1, #2, etc.)

Of couse you could have defined goesInto24Q directly, without any pure function at all:

	goesInto24Q[d_]:=goesIntoQ[d,24]

If you were going to be checking what "goes into" 24 a lot, of course you would introduce a name for this function. But if you're going to use the function only once or twice, you might as well just use the pure function as a "throw-away", without ever giving it a name.

To check your understanding of pure functions, try these (optional) exercises.