Let *n* be the product of three consecutive positive integers. Show that there is an integer *s*, greater than the smallest of the consecutive integers, such that *n* is divisible by *s*^{2}-1.

Solution:

## Posts Tagged ‘Number Theory’

### Monday Math 137

September 27, 2010### Monday Math 86

August 24, 2009A notable multiplicative function is the Möbius function *μ*(*n*) defined as follows:

*μ*(*n*)=1 when n is a square-free integer with an even number of distinct prime factors

*μ*(*n*)=-1 when n is a square-free integer with an odd number of distinct prime factors

*μ*(*n*)=0 when n is not square-free.

Note that *μ*(1)=1, as 1 has an even number of prime factors; namely, zero.

In terms of the distinct prime factor counting function *ω*(*n*) (see here), we can write the Möbius function as:

One can easily confirm that *μ*(*n*) is a multiplicative function (but not a completely multiplicative function); if either *m* or *n* is not square-free (or both), then *mn* is not square-free [and *μ*(*mn*)=*μ*(*m*)*μ*(*n*)=0]. If *m* and *n* are both square-free and coprime, they have no common prime factors, so *mn* is square-free and *ω*(*mn*)=*ω*(*m*)+*ω*(*n*) [so ].

In terms of the powers of primes, we see:

.

### Monday Math 85

August 17, 2009In number theory, an arithmetic function *f*(*n*) is called a multiplicative function if it possesses the property that *f*(*ab*)=*f*(*a*)*f*(*b*) for any positive integers *a* and *b* which are coprime (gcd(*a*,*b*)=1). Note that since gcd(*n*,1)=1 for any positive integer *n*, we see that for any multiplicative function, *f*(1)=1.

If the property *f*(*ab*)=*f*(*a*)*f*(*b*) holds for all positive integers *a* and *b*, coprime or not, then the function is said to be completely multiplicative.

One example of a multiplicative function is Euler’s totient function *φ*(*n*) (some others may be found here).

Now, consider the prime factorization of *n*:

. Plugging this into a multiplicative function, we see:

.

Thus, a multiplicative function is determined completely by its values for the powers of the prime numbers. This simplifies the computation of multiplicative functions. For example, consider *φ*(*n*). For a power of a prime *p ^{k}*,

*k*>0, the only positive integers less than or equal to this number which

*aren’t*coprime with it are multiples of

*p*:

*p*, 2

*p*, 3

*p*, … , (

*p*

^{k-1})

*p*=

*p*; this is

^{k}*p*

^{k-1}numbers, so the totient is

. This allows us to compute the totient of any number from it’s prime factorization, e.g.:

*φ*(720)=

*φ*(2

^{4}3

^{2}5)

=

*φ*(2

^{4})

*φ*(3

^{2})

*φ*(5)

=2

^{4-1}(2-1)·3

^{2-1}(3-1)·5

^{1-1}(5-1)

=8·6·4=192

Let

*f*(

*n*) and

*g*(

*n*) be multiplicative functions, and let

*h*(

*n*)=

*f*(

*n*)

*g*(

*n*) be their product. Then for any coprime positive integers

*a*and

*b*,

,

so the product of two multiplicative functions is multiplicative.

### Monday Math 65

March 30, 2009Divisibility Tests Part 5: Tests for 13

Divisibility tests for 13 are also quite rare, however we can create a test analogous to our first for 7.

We note that 9*10+1=91=7*13, so with *n*=10*a*+*b* and *q*=*a*-9*b*, we see

,

so 9*n*+*q* is a multiple of 13, which means that *n* is divisible by 13 if and only if *q* is divisible by 13. This gives us the test: mulitply the ones digit of our number by 9, and subtract from the number formed by the rest of the digits. We see that this doesn’t work well for two-digit numbers, but a little better for three- or four-digit numbers.

For example:

*n*=78

7-8*9=-65=-5*13

*n*=182

18-2*9=0=0*13

*n*=507

50-7*9=-13

*n*=3679

367-9*9=286

28-9*6=-26=-2*13

so all of these numbers are divisible by 13.

As with 7, this procedure may be laborious for very large numbers. However, we can see that

1001=7*143=7*11*13=77*13

This means 1000=13*77-1, and so we see our large-number divisibility test for 7 also works for 13.

Thus, we split our large number into sets of three digits, and then take the alternating sum of these numbers. For example:

*n*=348,970,129,352

352-129+970-348=845

84-5*9=39=3*13

so 348,970,129,352 is divisible by 13

*n*=4,626,145,317,014,712

712-14+317-145+626-4=1492

149-2*9=131=13*10+1, which is not divisible by 13,

so 4,626,145,317,014,712 is not divisible by 13.

### Monday Math 64

March 23, 2009Divisibility Tests Part 4: Tests for 7

One generally does not see tests for divisibility by 7, as these aren’t as simple or quick as the more common tests. However, tests do exist.

First, let us consider two numbers *a* and *b*, and examine *n*=10*a*+*b*, *q*=*a*-2*b*. In particular,

, so 2*n*+*q* is a multiple of 7, which means that *n* is divisible by 7 if and only if *q* is divisible by 7. This gives us the following test: mulitply the ones digit of our number by 2, and subtract from the number formed by the rest of the digits.

For example:

*n*=42

4-2*2=0=0*7

*n*=49

4-2*9=4-18=-14=-2*7

*n*=301

30-2*1=28=4*7

so all of these numbers are divisible by 7.

For large numbers, we can repeat the test:

*n*=41,237

4123-2*7=4109

410-2*9=392

39-2*2=35=5*7,

so 41,237 is divisible by 7 (41,237=7*5891)

Note that for very large numbers, the procedure may be laborious. However, we can develop a second test by noting that

1001=7*143

This means 1000=7*143-1, and so:

,

and so on, so that

is divisible by 7 for all non-negative integers *k*. This creates a test by analogy to our divisibility test for 11.

Thus, we split our large number into sets of three digits, and then take the alternating sum of these numbers. For example:

*n*=348,967,129,356,874

874-356+129-967+348=28=4*7

so 348,967,129,356,874 is divisible by 7.

We can also combine the tests:

*n*=1,626,145,217,013,712

712-13+217-145+626-1=1596

159-2*6=147=21*7

so 1,626,145,217,013,712 is divisible by 7

### Monday Math 63

March 16, 2009Divisibility tests Part 3: 11

Last time, we proved the tests for divisibility by 3 and 9. Now, for 11, we again use the factoring rule . We also use the rule that if *n* is odd.

The first tells us , and so is divisible by 11 (as 99=11*9) for even *k*.

The second tells us that

.

So is divisible by 11 for all non-negative integers *k*.

So we consider the alternating sum . The difference between *n* and *a* is then

, and as each term of the series is divisible by 11, the difference is a multiple of 11. Thus, *n* is divisible by 11 if and only if *a* is a multiple of 11.

An few examples of this test:

*n*=297: 7-9+2=0=0*11, so 297 is divisible by 11 (297=27*11)

*n*=12,529:

9-2+5-2+1=11 (12,529=1139*11)

*n*=4,596,836:

6-3+8-6+9-5+4=13, so 4,596,836 is not divisible by 11.

*n*=94,949,690:

0-9+6-9+4-9+4-9=-22=-2*11, so 94,949,690 is divisible by 11 (94,949,690=8,631,790*11).

### Monday Math 62

March 9, 2009**Divisibility Tests**

**Part 2: 3 and 9**

One may know that the tests for divisibility by 3 and 9 involve adding the digits of a number: a number is divisible by 3 if and only if the sum of its digits is divisible by 3, and divisible by 9 if and only if the sum of its digits is divisible by 9.

The key is to recall the factoring rule , used to prove the geometric series formulas. This means that . (This just means 9, 99, 999, 9999, etc. are all multiples of 9, which should be quite obvious).

Let us consider an integer *n*. Let *a*_{0} be the ones digit, *a*_{1} the tens digit, *a*_{2} the hundreds digit, and so on, with *a _{m}* the highest digit, so that

*n*is an (

*m*+1)-digit number. This means

. The sum of the digits, in turn, is . The difference between these two is

.

As this is a multiple of 9, we see that

*n*is divisible by 9 if and only if

*s*is divisible by 9, and as a multiple of 9 is also a multiple of 3,

*n*is divisible by 3 if and only if

*s*is divisible by 3.

### Monday Math 34

August 25, 2008Today, we have another bit of number theory: what are the positive integers *n* such that *n*^{3}+1 is prime?

Well, we recall that *a*^{3}+*b*^{3}=(*a*+*b*)(*a*^{2}–*a**b*+*b*^{2}). Thus, *n*^{3}+1=(*n*+1)(*n*^{2}–*n*+1).

Now, for *n*^{3}+1 to be prime, one of those factors must be equal to one. For positive n, *n*+1>1, and so we have *n*^{2}–*n*+1=1, which means

*n*^{2}–*n*=0

*n*(*n*-1)=0

which, for positive *n*, gives only *n*=1, for *n*^{3}+1=1^{3}+1=2 prime. All other positive *n* give composite numbers.

### Monday Math 32

August 11, 2008Today we have a bit of number theory. Let *n* be an integer greater than one. Then if is prime, it can be expressed in the form , for some integer *k*.

Proof: we have that if is prime, for some integer *k*. The latter equation is the same as , which has a solution for integer *k* if and only if *n* is even. Now, we see that if *n* is odd, then is odd, and so is even. Since *n*>1, , and thus we see if *n* is odd, cannot be prime. Thus, if is prime, *n* is even, and so is divisible by four, and thus can be expressed in the form .