# Divisors

## Divisors Topics

Sort by:

### Divisible

A number is said to be divisible by if is a divisor of .The function Divisible[n, d] returns True if an integer is divisible by an integer .The product of any consecutive integers is divisible by . The sum of any consecutive integers is divisible by if is odd, and by if is even.

### Unitary divisor function

The unitary divisor function is the analog of the divisor function for unitary divisors and denotes the sum-of-th-powers-of-the-unitary divisors function. As in the case of the usual divisor function, is commonly written .The numbers of unitary divisors is the same as the numbers of squarefree divisors of , as well as , where is the number of different primes dividing .If is squarefree, then . can be computed using the formulawhich can be computed in the Wolfram Languageas UnitaryDivisorSigma[k_, n_Integer] := Times @@ (1 + (Power @@@ FactorInteger[n])^k)The following table gives for , 2, ... and small .OEIS for , 2, ...0A0344441, 2, 2, 2, 2, 4, 2, 2, 2, 4, 2, 4, 2, 4, 4, 2, 2, 4, 2, 4, ...1A0344481, 3, 4, 5, 6, 12, 8, 9, 10, 18, 12, 20, 14, 24, 24, ...2A0346761, 5, 10, 17, 26, 50, 50, 65, 82, 130, 122, 170, 170, 250, 260, ...3A0346771, 9, 28, 65, 126, 252, 344, 513, 730, 1134, 1332, 1820, ...4A0346781, 17, 82, 257, 626, 1394, 2402, 4097, 6562, 10642, .....

### Unitary divisor

A divisor of for which(1)where is the greatest common divisor. For example, the divisors of 12 are , so the unitary divisors are . A list of unitary divisors of a number an be computed in the Wolfram Language using: UnitaryDivisors[n_Integer] := Sort[Flatten[Outer[ Times, Sequence @@ ({1, #}& /@ Power @@@ FactorInteger[n]) ]]]The following table gives the unitary divisors for the first few integers (OEIS A077610).1121, 231, 341, 451, 561, 2, 3, 671, 781, 891, 9101, 2, 5, 10111, 11121, 3, 4, 12131, 13141, 2, 7, 14151, 3, 5, 15Given the prime factorization(2)then(3)is a unitary divisor of if each is 0 or . For a prime power , the unitary divisors are 1 and (Cohen 1990).The symbol is used to denote to the unitary divisor function.The numbers of unitary divisors of , 2, ... are 1, 2, 2, 2, 2, 4, 2, 2, 2, 4, 2, 4, 2, 4, 4, 2, 2, 4, 2, 4, ... (OEIS A034444). These numbers are also the numbers of squarefree divisors of . The number of unitary divisors of is also given..

### Divides

If, for and integers, the ratio is itself an integer, then is said to divide . This relationship is written , read " divides ." In this case, is also said to be divisible by and is called a divisor of .Clearly, and . By convention, for every except 0 (Hardy and Wright 1979, p. 1).The function can be implemented in the Wolfram Language as Divides[a_, b_] := Mod[b, a] == 0The function Divisible[n, d] returns True if an integer is divisible by an integer .

### Leudesdorf theorem

Let denote the set of the numbers less than and relatively prime to , where is the totient function. Then if(1)then(2)

### Divisibility tests

In general, an integer is divisible by iff the digit sum is divisible by .Write a positive decimal integer out digit by digit in the form . The following rules then determine if is divisible by another number by examining the congruence properties of its digits. In congruence notation, means that the remainder when is divided by a modulus is . (Note that it is always true that for any base.) 1. All integers are divisible by 1. 2. , so for . Therefore, if the last digit is divisible by 2 (i.e., is even), then so is . 3. , , , ..., (mod 3). Therefore, if the digit sum is divisible by 3, so is (Wells 1986, p. 48). In general, if the sum of any permutation of the digits of in any order is divisible by 3, then so is . 4a. , , ..., (mod 4). So if the last two digits are divisible by 4, then so is . 4b. If is, then so is . 5. , so for . Therefore, if the last digit is divisible by 5 (i.e., is 5 or 0), then so is . 6a. If is divisible by 3 and is even, then is also divisible by 6. 6b. , , ..., (mod 6)...

### Korselt's criterion

divides for all integers iff is squarefree and for all prime divisors of . Carmichael numbers satisfy this criterion.

### Infinitary divisor

is an infinitary divisor of (with ) if , where denotes a k-ary Divisor (Guy 1994, p. 54). Infinitary divisors therefore generalize the concept of the k-ary divisor.Infinitary divisors can also be defined as follows. Compute the prime factorization for each divisor of ,Now make a table of the binary representations of for each prime factor . The infinitary divisors are then those factors that have zeros in the binary representation of all s where itself does. This is illustrated in the following table for the number , which has divisors 1, 2, 3, 4, 6, and 12 and prime factors 2 and 3.1200003000022100130000320000310014220103000062100131001122201031001As can be seen from the table, the divisors 1, 3, 4, and 12 have zeros in the binary expansions of (the exponents of 2) in the positions that 12 itself does. Similarly, all divisors have zeros in the leftmost two positions in the binary expansions of (the exponents of 3), as does 12 itself. The intersection..

### Honaker's problem

Honaker's problem asks for all consecutive prime number triples with such that . Caldwell and Cheng (2005) showed that the only Honaker triplets for are (2, 3, 5), (3, 5, 7), and (61, 67, 71). In addition, Caldwell and Cheng (2005) showed that the Cramér-Granville conjecture implies that there can only exist a finite number of such triplets, that implies there are exactly three, and conjectured that these three are in fact the only such triplets.

### Greatest dividing exponent

The greatest dividing exponent of a base with respect to a number is the largest integer value of such that , where . It is implemented as the Wolfram Language function IntegerExponent[n, b].

### Carefree couple

Define a carefree couple as a pair of positive integers such that and are relatively prime (i.e., ) and is squarefree. Similarly, define a strongly carefree couple as a pair such that and both and are squarefree, and a weakly carefree couple as a pair such that and at least of one and is squarefree.Let be the number of squarefree pairs, the number of carefree couples, the number of strongly carefree couples, and the number of weakly squarefree couples with , illustrated above.The numbers of squarefree pairs for , 2, ... are 1, 3, 7, 11, 19, 23, 35, 43, 55, ... (OEIS A018805), which has closed forms(1)(2)where is the totient summatory function, is the floor function, and is the Möbius function.The numbers of carefree couples for , 2, ... are 1, 3, 7, 9, 16, 20, 31, 35, 39, ... (OEIS A118258); the numbers of strongly carefree couples are 1, 3, 7, 7, 13, 17, 27, 27, ... (OEIS A118259); and the numbers of weakly carefree couples are 1, 3, 7, 11, 19, 23, 35, 43, 51,..

### Relatively prime

Two integers are relatively prime if they share no common positive factors (divisors) except 1. Using the notation to denote the greatest common divisor, two integers and are relatively prime if . Relatively prime integers are sometimes also called strangers or coprime and are denoted . The plot above plots and along the two axes and colors a square black if and white otherwise (left figure) and simply colored according to (right figure).Two numbers can be tested to see if they are relatively prime in the Wolfram Language using CoprimeQ[m, n].Two distinct primes and are always relatively prime, , as are any positive integer powers of distinct primes and , .Relative primality is not transitive. For example, and , but .The probability that two integers and picked at random are relatively prime is(1)(OEIS A059956; Cesàro and Sylvester 1883; Lehmer 1900; Sylvester 1909; Nymann 1972; Wells 1986, p. 28; Borwein and Bailey 2003, p. 139;..

### Euclid's lemma

For any two integers and , suppose . Then if is relatively prime to , then divides . This results appeared in Euclid's Elements, Book VII, Proposition 30.This result is incorrectly termed "Gauss's lemma,"which is an entirely different result, by Séroul (2000, pp. 10-11).

### Biunitary divisor

A divisor of a positive integer is biunitary if the greatest common unitary divisor of and is 1. For a prime power , the biunitary divisors are the powers 1, , , ..., , except for when is even (Cohen 1990).

### Divisor

A divisor, also called a factor, of a number is a number which divides (written ). For integers, only positive divisors are usually considered, though obviously the negative of any positive divisor is itself a divisor. A list of (positive) divisors of a given integer may be returned by the Wolfram Language function Divisors[n].Sums and products are commonly taken over only some subset of values that are the divisors of a given number. Such a sum would then be denoted, for example,(1)Such sums are implemented in the Wolfram Language as DivisorSum[n, form, cond].The following tables lists the divisors of the first few positive integers (OEISA027750).divisors1121, 231, 341, 2, 451, 561, 2, 3, 671, 781, 2, 4, 891, 3, 9101, 2, 5, 10111, 11121, 2, 3, 4, 6, 12131, 13141, 2, 7, 14151, 3, 5, 15The total number of divisors for a given number (variously written , , or ) can be found as follows. Write a number in terms of its prime factorization(2)For any divisor..

### B&eacute;zout numbers

Integers for and that satisfy Bézout's identityare called Bézout numbers. For integers , ..., , the Bézout numbers are a set of numbers , ..., such thatwhere is the greatest common divisor of , ..., .