A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. 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 , , , be integers, such that . Given that | | (6) | show that is not a prime number. By rearranging equation (6), we have Let us use this form from now on.
Solution 1: Substitute. The proof is indirect. Assume that , where is a prime. We have the simultaneous equations | | (8) | 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 . According to the second equation, . Multiply equation (7) by , and substitute for : | | 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 , and is divisible by , as we assumed that was a prime. The numbers and are positive and less than , and thus cannot be divisible by . There remains the only possibility that is divisible by . As | | the number can only be divisible by if it equals . Hence the simultaneous equations to solve are | | (9) | No it is easy to show the contradiction. Consider equation (9) modulo (as is the largest one of the unknowns). It follows that is divisible by . But that is impossible, as and are relative primes (or otherwise could not be a prime), and .
Solution 2: With a little help from Euler. It is clear to anyone who has read about them that equation (7) is closely related to Eulerian integers. Let be a complex third root of unity. The complex numbers of the form , where and are integers, are called Eulerian integers. Eulerian integers form lattice of regular triangles in the complex plane (Figure 1).
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 : | |
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 is the number . There is a very important quantity called the norm of an Eulerian integer. The norm of an Eulerian integer is denoted by and defined as follows: 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: An Eulerian integer is a factor of an Eulerian integer if there exists an Eulerian integer such that . It follows from the multiplicativity of the norm that if then . (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 . A non-unit Eulerian integer is said to be irreducible if its only factors are the units and itself. A non-unit and non-zero Eulerian integer is said to be a prime if implies or for any Eulerian integers , . 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 are also Eulerian primes. The primes of the form can be reduced to the product of two non-associate Eulerian primes (e.g. ). The prime factor decomposition of 3 is . |
The theorems show that there is a close relationship between the prime factors of an Eulerian integer and the prime factors of . The square of each prime factor of occurs in the prime factor decomposition of , and so do the norms of all the other prime factors, which are either 3 or primes of the form . For example, let . Its resolution into Eulerian primes is and that of its norm is . Conversely, the prime factors of ``almost determine" the prime factors of . All prime factors of are also prime factors of (with half the exponent), and each factor of 3 in the resolution of is the norm of the Eulerian prime . The prime factors of are also norms of prime factors of , but there are two possible Eulerian primes in each case, even if associates are not considered different.
Back to the problem: let and . According to the given condition, , that is, . We have to prove that , that is, the ``real part'' of , cannot be a prime. As , 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) | where and are Eulerian primes and , are units. Let and as above. Then (It may happen that there are only common or only different prime factors in and ; then, of course , or .) Consider now the number | | (11) | This number is divisible by , and thus and are also divisible by . What remains to prove is that neither nor is possible. If , that is , then and are associates, which means that they can be obtained from each other by a few rotations about 0. The number of these rotations is determined by the arguments of and .
Figure 2 It follows from the condition that the argument of is between and , and that of is between and (Figure 2). Thus the difference of the arguments is between and , and hence the angle of rotation is exactly , that is . But then, | | which is impossible, as . Thus the assumption leads to a contradiction. If , then by dividing equation (11) by we get | | This number, as shown by the right-hand side, is an Eulerian integer. Its argument is the sum of the arguments of and , which is between and , and its ``real part'' is , by assumption. The only Eulerian integer satisfying this requirement is 1 (Figure 3), hence and .
Figure 3 Thus the product of the numbers and is the positive real number . As , it follows that the two numbers are conjugates. But then
| | which is impossible, as . The assumption 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 , , , with and All we need to do is find Eulerian integers of the appropriate arguments. For example, setting | | , , and , with (Obviously, is not a prime.)
|