Nhờ dịch giùm một bài toán

[light_future96]

Solution. Suppose m,n is such a pair. Clearly n< m.Step 1. We claim that is exactly divisible by in. Indeed, since is monic, the division algorithm givesf (x) = xm + x − 1 g (x) = xn + x2 − 1Z[x] g (x)f (x) / g (x) = q (x) + r (x) / g (x)where . The remainder term tends to zero as ; on the otherhand it is an integer at infinitely many integers . Thus infinitely often, and so. The claim follows; and in particular, we note that is an integer for allintegers .deg (r) < deg (g) r (x) / g (x) x → ∞a r(a) / g (a) = 0r ≡ 0 f (a) / g (a)aStep 2. Both and have a unique root in the interval (0, 1), since both functions areincreasing in [0, 1] and span the range . Moreover it is the same root, since divides ;call it .f (x) g (x)[−1, 1] g fαStep 3. We can use to show that . Certainly , where is the positiveroot of . This is because is increasing in (0, 1) and .On the other hand, if then , and the outer terms rearrangeto give , which requires , a contradiction.α m < 2n α >φ φ= 0.618…h(x) = x2 + x − 1 f f(φ) < h(φ) = 0 = f (α)m ≥ 2n 1 − α = αm ≤ (αn)2 = (1 − α2)2α (α − 1) (α2 + α − 1) ≥ 0 α ≤ φStep 4. We show that the only solution with is . This is pure numbertheory, at last. Suppose we have a solution. We consider the value , and write, so that . Let where , so thatm < 2n (m, n) = (5, 3)a = 2d = g (2) = 2n + 3 −2m ≡ 1 (mod d) m = n + k 1 ≤ k < n−2m ≡ (d − 2n)2k ≡ 3 × 2k (mod d) ,which shows that when . When , that is, the least positive residue (mod ) for is given by ,which takes the value 1 only when , giving . Finally, the identityshows that is indeed a solution.2/Comment1. The natural strategy for this problem is to use induction on the number of primes involved,hoping that the number of divisors increases by a factor of 4 for each new prime in theexpression. By the usual properties of the divisor function , it would be enough toshow that contains at least two new prime factors not contained in .Unfortunately this does not seem to be easy. Instead, we will show in an elementary waythat there is at least one new prime at each step. To finish the proof, we will need thefollowing additional observation: if then , which follows from thesimple fact that if divides then both and divide .d (m)2p1p2…pn +1 2p1p2…pn − 1 + 1k >m d(km) ≥ 2d (m)a m a ka kmSolution. We claim first that if and are coprime odd numbers then the highest commonfactor of and is 3. Certainly 3 divides and , because and are odd.Suppose now that some divides and . Then we have and. But if any is then the set of all such is the set of all oddmultiples of , where is the order of . It follows that divides both and ,which is impossible as .u v2u +1 2v +1 2u +1 2v + 1 u vt > 3 2u +1 2v +1 2u ≡ −1 (mod t)2v ≡ −1 (mod t) 2x −1 modt xr / 2 r 2 modt r/ 2 u vr > 2Note also that the factorisation2uv + 1 = (2u + 1)(2u(v − 1) − 2u(v − 2) + … + 22u − 2u + 1)shows that is divisible by and , and so is also divisible by.2uv +1 2u +1 2v + 1(2u + 1) (2v + 1)/ 3Let us now prove the desired result by induction on . It is certainly true when (forexample, because is a multiple of 3 and is at least 27), so we assume thathas at least divisors and consider . Setting and in theabove, we see that and are coprime, whence hasat least divisors.n n= 12p1 +1 2p1…pn − 1 + 14n − 1 2p1…pn + 1 u = p1… pn − 1 v = pn2u + 1 (2v + 1)/ 3 m = (2u + 1) (2v + 1)/ 32 × 4n − 1Now, we know that divides . Moreover, from when , wesee that . By the fact mentioned in the comment above, it follows thatm 2uv + 1 uv > 2 (u + v) u, v ≥ 52uv + 1 > m2d (2uv + 1) ≥ 2d (m) ≥ 4n, as required.Further comment2. From a more advanced point of view, is the product of cyclotomic polynomialsat 2, that is the product of over . It turns out that and arecoprime unless is a prime power (this is not an easy fact), from which it follows thathas at least prime divisors. Hence , which ismuch more than when is large.