(New page: =The Erdos-Woods Problem= ==Setup== '''Fundamental Theorem of Arithmetic''': Every integer $n >1$ can be expressed uniquely as a product $$n = p_1^{e_1} \cdots p_k^{e_k}$$ where the $p_i$...) |
|||
| Line 1: | Line 1: | ||
| − | =The Erdos-Woods Problem= | + | = The Erdos-Woods Problem = |
| − | + | This page introduces a problem considered by Erdos and Woods. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | '''Defintion (Radical)''': The | + | '''Defintion (Radical)''': The radical of a positive integer n is simply the product of all those prime numbers p which divide n. |
| − | '''Remark''': The only reasonable | + | '''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):<br>....: return prod(n.prime_divisors())<br>....: <br>sage: rad(256)<br>2<br>sage: rad(210)<br>210<br><br> | |
| − | "'''I'm going to pick a positive integer $n | + | The rad(n) is a function with some very nice properties. It also behaves well with respect to the function gcd(A,B). |
| + | |||
| + | '''Exercise 1:''' Show that: | ||
| + | |||
| + | (a) gcd(rad(A),rad(B)) = rad(gcd(A,B)) | ||
| + | |||
| + | (b) 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... | For which $k$ should you accept this challenge? Discuss... | ||
Revision as of 09:21, 22 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).
Exercise 1: Show that:
(a) gcd(rad(A),rad(B)) = rad(gcd(A,B))
(b) 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...
