Revision as of 14:45, 23 July 2010

The Erdos-Woods Problem

This page introduces a problem considered by Erdos and Woods.

Defintion (Radical): The radical of a positive integer n is simply the product of all those prime numbers p which divide n.

Remark: There are no prime numbers which divide 1, so rad(1) is the product of all the elements in the empty set. The only reasonable value to choose for this number is 1.

To compute rad(n) in sage, define the following simple function.

sage: def rad(n):
....: return prod(n.prime_divisors())
....:
sage: rad(256)
2
sage: rad(210)
210

The rad(n) is a function with some very nice properties. It also behaves well with respect to the function gcd(A,B).

Proposition / Definition (Squarefree) Let $n > 0$ be an integer. The following are equivalent:

(a) $\text{rad}(n) = n$

(b) There does not exist an integer $d > 1$ such that $d^2$ divides $n$.

Exercise 1: Suppose that A and B are positive integers. Show that:

gcd(rad(A),rad(B)) = rad(gcd(A,B))

and

rad(AB) = rad(A)rad(B)/rad(gcd(A,B))

The Evil Wizard

Suppose you are confronted by an evil wizard who presents you with the following challenge:

"I'm going to pick a positive integer $n > 1$ and then I shall tell you the radical of each integer from $n$ to $n+k$. Then you must tell me what $n$ is."

For which $k$ should you accept this challenge? Discuss...