KöMaL: Angol szám, 2002. december

	Angol nyelvű szám, 2002. december
	Előző oldal	Tartalomjegyzék	Következő oldal	MEGRENDELŐLAP

Remarks to the Olympiad

Géza Kós

We investigate Problem 6 of the International Mathematical Olympiad of this year. This article presents two solutions.

The first one, like the solution of Problem 2, does not make use of any special idea, and does not require anything beyond high-school mathematics, but it starts with a surprising step that might look discouraging at the first sight.

The second solution requires much more mathematical background. It uses as extension of the set of integers, the theory of the so-called Eulerian integers. This is the price for revealing the most probable origin of the problem.

Problem 6. Let a, b, c, d be integers, such that a>b>c>d>0. Given that

(6)	ac+bd= (b+d+a-c)(b+d-a+c),

show that ab+cd is not a prime number.

By rearranging equation (6), we have

(7)	a²-ac+c²=b²+bd+d².

Let us use this form from now on.

Solution 1: Substitute.

The proof is indirect. Assume that ab+cd=p, where p is a prime. We have the simultaneous equations

(8)	a²-ac+c²= b²+bd+d², ab+cd=p.

The number of unknowns and equations can be reduced by expressing some appropriate expression out of one equation and substituting it into the other. In order to make calculations more convenient, let us consider everything modulo p.

According to the second equation, ab$\displaystyle \equiv$-cd (mod p). Multiply equation (7) by b², and substitute -cd for ab:

c0 = b²(b²+bd+d²-a²+ac-c²)= b⁴+b³d+b²d²-(ab)²+ab^.bc- b²c² $\displaystyle \equiv$
$\displaystyle \equiv$b⁴+b³d+b²d²- (cd)²- cd^.bc- b²c²=(b+c)(b-c)(b²+bd+d²) (mod p).

The resulting expression is a product of three factors, one of which is equal to the quantity in equation (7). It follows from the congruence that one of the three factors b+c, b-c and b²+bd+d² is divisible by p, as we assumed that p was a prime. The numbers b+c and b-c are positive and less than ab+cd=p, and thus cannot be divisible by p. There remains the only possibility that b²+bd+d² is divisible by p. As

0<b²+bd+d²< ab+ab+cd< 2(ab+cd)= 2p,

the number b²+bd+d² can only be divisible by p if it equals p. Hence the simultaneous equations to solve are

(9)	a²-ac+c²= b²+bd+d²= ab+cd=p.

No it is easy to show the contradiction. Consider equation (9) modulo a (as a is the largest one of the unknowns). It follows that c(c-d)= ab+ac-a² is divisible by a. But that is impossible, as a and c are relative primes (or otherwise ab+cd could not be a prime), and 0<c-d<a.

Solution 2: With a little help form Euler.

Figure 1

It is clear to anyone who has read about them that equation (7) is closely related to Eulerian integers.

Let $\displaystyle \varrho$ be a complex third root of unity. The complex numbers of the form x+y$\displaystyle \varrho$, where x and y are integers, are called Eulerian integers. Eulerian integers form a lattice of regular triangles in the complex plane (Figure 1).

This number set has several remarkable and useful properties. Leonhard Euler also used these numbers when he proved Fermat's last theorem for the exponent 3. Let us briefly summarize the most important concepts and theorems related to Eulerian integers that will be needed in the proof.

Addition, subtraction and multiplication of Eulerian integers are defined in the natural way. Remember that $\displaystyle \varrho$²= -$\displaystyle \varrho$-1:

rcl(x+y$\displaystyle \varrho$)$\displaystyle \pm$(u+v$\displaystyle \varrho$) & = & (x$\displaystyle \pm$u)+ (y$\displaystyle \pm$v)$\displaystyle \varrho$;
(x+y$\displaystyle \varrho$)(u+v$\displaystyle \varrho$) = xu+ (xv+yu)$\displaystyle \varrho$+ yv$\displaystyle \varrho$² & = &(xu-yv)+ (xv+uy-yv)$\displaystyle \varrho$.

The commutative, associative and distributive properties of addition and multiplication of integers or real numbers are also valid for Eulerian integers. The properties of the numbers 0 and 1 also remain valid: for example if 0 is added to any Eulerian integer, the sum equals the original number, or 0 times any Eulerian integer is 0.

The conjugate of an Eulerian integer $\displaystyle \alpha$=x+y$\displaystyle \varrho$ is the number $\displaystyle \overline{\alpha}=x+y\varrho^2=(x-y)-y\varrho$.

There is a very important quantity called the norm of an Eulerian integer. The norm of an Eulerian integer $\displaystyle \alpha$=x+y$\displaystyle \varrho$ is denoted by N($\displaystyle \alpha$) and defined as follows:

$\displaystyle N(\alpha)=\alpha\cdot\overline{\alpha}=x^2-xy+y^2. $

The norm is always a non-negative integer, and 0 is the only number whose norm is 0.

The norm is clearly equal to the square of the modulus of the complex number. Thus the norm of a product is the product of the norms of the factors:

N($\displaystyle \alpha$^.$\displaystyle \beta$)=N($\displaystyle \alpha$)^.N($\displaystyle \beta$).

An Eulerian integer $\displaystyle \alpha$ is a factor of an Eulerian integer $\displaystyle \beta$ if there exists an Eulerian integer $\displaystyle \gamma$ such that $\displaystyle \alpha$ $\gamma$ = $\beta$ . It follows from the multiplicativity of the norm that if $\alpha$ | $\beta$ then N( $\alpha$ )|N( $\beta$ ). (The latter divisibility is meant in the set of rational integers.)

There are six Eulerian integers whose norm is 1. They are called units and marked in Figure 1. The units divide all Eulerian integers.

Two Eulerian integers are said to be associate if they are obtained from each other by multiplication with a unit, that is, by rotation about 0 through a multiple of 60^o.

A non-unit Eulerian integer $\pi$ is said to be irreducible if its only factors are the units and itself.

A non-unit and non-zero Eulerian integer $\pi$ is said to be a prime if $\pi$ | $\alpha$ $\beta$ implies $\pi$ | $\alpha$ or $\pi$ | $\beta$ for any Eulerian integers $\alpha$ , $\beta$ . In order to distinguish the primes in the system of Eulerian integers from real primes, let us call them Eulerian primes.

The most important theorems of the theory of Eulerian integers are the following

[1.] Irreducible Eulerian integers are the same as Eulerian primes.

[2.] The fundamental theorem of number theory is valid for Eulerian integers, too: Every non-zero and non-unit Eulerian integer can be expressed as a product of Eulerian primes and units, and the representation is unique up to associates, that is, in any two representations, the corresponding factors are associates of each other.

[3.] The real primes of the form 3k+2 are also Eulerian primes. The primes of the form 3k+1 can be reduced to the product of two non-associate Eulerian primes (e.g. 7=(3+ $\varrho$ )(2- $\varrho$ )). The prime factor decomposition of 3 is 3=- $\varrho$ ²(1- $\varrho$ )².

The theorems show that there is a close relationship between the prime factors of an Eulerian integer $\alpha$ and the prime factors of N( $\alpha$ ). The square of each prime factor 3k+2 of $\alpha$ occurs in the prime factor decomposition of N( $\alpha$ ), and so do the norms of all the other prime factors, which are either 3 or primes of the form 3k+1.

For example, let $\alpha$ =10+8 $\varrho$ . Its resolution into Eulerian primes is 2^.(2+ $\varrho$ )(3+ $\varrho$ ) and that of its norm is N( $\alpha$ )=N(2)^.N(2+ $\varrho$ )^.N(3+ $\varrho$ )=2²^.3^.7.

Conversely, the prime factors of N( $\alpha$ ) ``almost determine" the prime factors of $\alpha$ . All prime factors 3k+2 of N( $\alpha$ ) are also prime factors of $\alpha$ (with half the exponent), and each factor of 3 in the resolution of N( $\alpha$ ) is the norm of the Eulerian prime 1- $\varrho$ . The prime factors 3k+1 of N( $\alpha$ ) are also norms of prime factors of $\alpha$ , but there are two possible Eulerian primes in each case, even if associates are not considered different.

Back to the problem: let $\alpha$ =a+c $\varrho$ and $\beta$ =b-d $\varrho$ . According to the given condition, a²-ac+c²=b²+bd+d², that is, N( $\alpha$ )=N( $\beta$ ). We have to prove that ab+cd, that is, the ``real part'' of $\alpha$ $\beta$ =(ab+cd)+ (bc+cd-ad) $\varrho$ , cannot be a prime.

As N( $\alpha$ )= N( $\beta$ ), the prime factors of the two Eulerian integers are ``almost the same". They have some prime factors in common, and the remaining factors are pairwise conjugate. This can be put as follows:

(10)	$\alpha=\varepsilon_1\cdot\pi_1\cdots\pi_k\cdot\mu_1\cdots\mu_l\quad{\mathrm and}\quad\beta=\varepsilon_2\cdot\pi_1\cdots\pi_k\cdot\overline{\mu}_1\cdots\overline{\mu}_l,$

where $\pi$ ₁,..., $\pi$ _k and $\mu$ ₁,..., $\mu$ _l are Eulerian primes and $\varepsilon$ ₁, $\varepsilon$ ₂ are units.

Let $\gamma$ = $\pi$ ₁^....^. $\pi$ _k and $\delta$ = $\mu$ ₁^....^. $\mu$ _l as above. Then

$\alpha$ = $\varepsilon$ ₁ $\gamma$ $\delta$ and $\beta=\varepsilon_2\gamma\overline{\delta}$ .

(It may happen that there are only common or only different prime factors in $\alpha$ and $\beta$ ; then, of course $\gamma$ =1, or $\delta$ =1.)

Consider now the number

(11)	$\alpha$ $\beta$ = (ab+cd)+ (bc+cd-ad) $\varrho$ = $\varepsilon$ ₁ $\varepsilon$ ₂ $\gamma$ ²^.N( $\delta$ ).

This number is divisible by N( $\delta$ ), and thus ab+cd and bc+cd-ad are also divisible by N( $\delta$ ). What remains to prove is that neither N( $\delta$ )=1 nor ab+cd=N( $\delta$ ) is possible.

If N( $\delta$ )= 1, that is $\delta$ =1, then $\alpha$ and $\beta$ are associates, which means that they can be obtained from each other by a few 60^o rotations about 0. The number of these rotations is determined by the arguments of $\alpha$ and $\beta$ .

It follows from the condition a>b>c>d>0 that the argument of $\alpha$ is between 0^o and 60^o, and that of $\beta$ is between -30^o and 0^o (Figure 2). Thus the difference of the arguments is between 0^o and 90^o, and hence the angle of rotation is exactly 60^o, that is $\alpha$ =(1+ $\varrho$ ) $\beta$ . But then,

$\alpha$ = a+c $\varrho$ = (1+ $\varrho$ ) (b-d $\varrho$ )= (b+d)+ b $\varrho$ ,

which is impossible, as b>c. Thus the assumption N( $\delta$ )=1 leads to a contradiction.


Figure 2	Figure 3

If ab+cd=N( $\delta$ ), then by dividing equation (11) by N( $\delta$ ) we get

$\frac{\alpha\beta}{N(\delta)}=\frac{ab+cd}{N(\delta)}+\frac{ad+bc-cd}{N(\delta)}\cdot\varrho=\varepsilon_1\varepsilon_2\cdot\gamma^2.$

This number, as shown by the right-hand side, is an Eulerian integer. Its argument is the sum of the arguments of $\alpha$ and $\beta$ , which is between -30^o and 60^o, and its ``real part'' is $\frac{ab+cd}{N(\delta)}=1$ , by assumption. The only Eulerian integer satisfying this requirement is 1 (Figure 3), hence $\varepsilon$ ₁ $\varepsilon$ ₂ $\gamma$ ²=1 and $\alpha$ $\beta$ = N( $\delta$ ).

Thus the product of the numbers $\alpha$ and $\beta$ is the positive real number N( $\delta$ ). As N( $\alpha$ )=N( $\beta$ ), it follows that the two numbers are conjugates. But then

$\alpha=a+c\varrho=\overline{\beta}=\overline{b-d\varrho}= b+d(1+\varrho)=(b+d)+d\varrho,$

which is impossible, as c>d. The assumption ab+cd= N( $\delta$ ) also leads to a contradiction. This completes the proof.

Solution 2 not only proves the statement of the problem, but also provides a construction for finding appropriate numbers a, b, c, d with a>b>c>d and

a²-ac+c²= b²+bd+d².

All we need to do is find Eulerian integers of the appropriate arguments.

For example, setting

$\alpha=a+c\varrho=(4+\varrho)(3+\varrho)=11+6\varrho,\quad\beta=b-d\varrho=(4+\varrho)\overline{(3+\varrho)}=9-\varrho,$

a=11, b=9, c=6 and d=1, with

a²-ac+c²= b²+bd+d²=91.

(Obviously, ab+cd=105 is not a prime.)

Már regisztráltál?
Új vendég vagy?

Angol nyelvű szám, 2002. december

Remarks to the Olympiad