Tuesday, September 13, 2011

Weird functions!

Here is another problem from IMO 2011, number 5 to be more precise:

Let ƒ be a function from the set of integers to the set of positive integers (Z+). Suppose that, for any two integers m and n, the diference ƒ(m)−ƒ(n) is divisible by ƒ(m−n), i.e. ƒ(m−n) | ƒ(m)−ƒ(n). Prove that, for all integers m and n with ƒ(m) ≤ ƒ(n), the number ƒ(n) is divisible by ƒ(m).

Weird indeed, but let's sort it out. We will consider that ƒ(m) < ƒ(n), because ƒ(m) = ƒ(n) case is straightforward. Let's prove some useful (and weird) properties of these functions first.

1. ƒ(m)=ƒ(m-0) | ƒ(m)-ƒ(0) ⇒ ƒ(m) | ƒ(0), for ∀m.

2. ƒ(-m)=ƒ(0-m) | ƒ(0)-ƒ(m). From (1) we know that ƒ(-m) | ƒ(0) which means:
- ƒ(-m) | ƒ(m) (*)
Similarly ƒ(m)=ƒ(0-(-m)) | ƒ(0)-ƒ(-m), which means:
- ƒ(m) | ƒ(-m) (**)
From (*), (**) and the fact that all the values returned by ƒ are positive ⇒ ƒ(-m) | ƒ(m) | ƒ(-m) ⇒ ƒ(-m)=ƒ(m), for ∀m.

3. From ƒ(n)>ƒ(m) (both are positive numbers) ⇒ ƒ(n)>ƒ(n)-ƒ(m)>ƒ(m)-ƒ(m)=0. But ƒ(n-m) | ƒ(n)-ƒ(m), which means, there ∃ an integer q≥1 so that q⋅ƒ(n-m)=ƒ(n)-ƒ(m) ⇒ ƒ(n)>ƒ(n)-ƒ(m)=q⋅ƒ(n-m)≥ƒ(n-m)>0.
From 0<ƒ(n-m)<ƒ(n) and 0<ƒ(m)<ƒ(n) results (from a≤b≤c≤d ⇒ |c-b|≤|d-a|):
- if ƒ(n-m)≤ƒ(m) ⇒ 0≤ƒ(m)-ƒ(n-m)<ƒ(n) or
- if ƒ(n-m)≥ƒ(m) ⇒ 0≤ƒ(n-m)-ƒ(m)<ƒ(n)
But both ƒ(m)-ƒ(n-m) and ƒ(n-m)-ƒ(m) are divisible by ƒ(n):
- ƒ(n)=ƒ(m-(m-n)) | ƒ(m)-ƒ(m-n)=(from 2)=ƒ(m)-ƒ(-(m-n))=ƒ(m)-ƒ(n-m)
- ƒ(n)=(from 2)=ƒ(-n)=ƒ((m-n)-m) | ƒ(m-n)-ƒ(m)=(from 2)=ƒ(-(m-n))-ƒ(m)=ƒ(n-m)-ƒ(m)
Or, saying it otherwise, ƒ(n) divides a positive number that is smaller than itself, which is possible only if the number is zero. In our case ƒ(n-m)-ƒ(m)=0 or ƒ(m)-ƒ(n-m)=0, which means ƒ(m)=ƒ(n-m).
As a result, if ƒ(n)>ƒ(m) ⇒ ƒ(m)=ƒ(n-m)

In the point 3 we stated that there ∃ an integer q≥1 so that q⋅ƒ(n-m)=ƒ(n)-ƒ(m), which is ⇔ q⋅ƒ(m)=ƒ(n)-ƒ(m) when ƒ(n)>ƒ(m) ⇔ ƒ(n)=(q+1)⋅ƒ(m) ⇔ ƒ(m) | ƒ(n)

Saturday, September 10, 2011

Alternative definition for the prime numbers

I was watching this video recently and mentioned the presenter pointing to the definition for the prime numbers we all know from the school, i.e.

Classical Definition: A natural number p > 1 is prime if 1 and p are its only divisors.

However, there is an alternative way to define the prime numbers (the one I learned when I was doing my university degree).

Alternative Definition: A natural number p > 1 is prime if for ∀ a, b - integers satisfying p | a⋅bp | a or p | b

(Note: "p | a" means "p divides a" or "a is divisible by p").

Sounds complicated? Not really. For example, according to this definition 4 isn't a prime because it divides 2⋅2, but doesn't divide 2.

With this definition, the classical one is, in fact, a theorem:

Theorem: A natural number p > 1 is prime ⇔ 1 and p are its only divisors.

Let's prove it ...

Step 1. Let's assume that p is prime and show that 1 and p are its only divisors.

We will start by supposing the contrary, i.e. there ∃ s,tN, both ∉ {1,p}, so that p=s⋅t. This means p | s⋅t and because p is prime ⇒ p | s or p | t. Let's assume p | ss=q⋅p, q - positive integer ⇒ p=s⋅t=q⋅p⋅t ⇒ 1=q⋅t which has sense when t=1 and q=1 ⇒ s=p - contradiction. So 1 and p are the only divisors for p - prime.

Step 2. Let's assume that the only divisors of p are {1, p} and show that p is prime.

Again we will suppose the contrary, i.e. p isn't prime. This means there ∃ a,b - integers so that p | a⋅b and p doesn't divide a and p doesn't divide b. We can write a⋅b=p⋅q, q - positive integer. We should note that (a,p) = 1 (greatest common divisor), otherwise if (a,p)=d>1 ⇒ d | p which means d = p and p | a - contradiction, so (a,p) = 1. From Bezout Theorem this means that there ∃ k,z - integers so that k⋅p+z⋅a=1 ⇔ k⋅p⋅b+z⋅a⋅b=bk⋅p⋅b+z⋅p⋅q=bp⋅(k⋅b+z⋅q)=b or p | b - contradiction. So p is prime.

It is important to note that if we consider the classical definition for the prime numbers, then the alternative definition becomes what is known as Euclid Lemma.

In other words, it doesn't really matter which definition we adopt (for integer numbers, for more details see this link), because one is provable from another.