uniolympiads English

IMC 2010, Ημέρα 1, Θέμα 4

Let a,ba, b be two integers and suppose that nn is a positive integer for which the set

Z∖{axn+byn∣x,y∈Z}\mathbb{Z} \setminus \big\{ax^n + by^n \mid x, y \in \mathbb{Z}\big\}

is finite. Prove that n=1n = 1.

Πρωτότυπο από το επίσημο PDFLet a, b be two integers and suppose that n is a positive integer for which the set Z \ ax n + by n | x, y ∈ Z is finite. Prove that n = 1.

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

Solution. Assume that n>1n>1. Notice that nn may be replaced by any prime divisor pp of nn. Moreover, aa and bb should be coprime, otherwise the numbers not divisible by the greatest common divisor of a,ba,b cannot be represented as axn+bynax^n+by^n.

If p=2p=2, then the number of the form ax2+by2ax^2+by^2 takes not all possible remainders modulo 8. If, say, bb is even, then ax2ax^2 takes at most three different remainders modulo 8, by2by^2 takes at most two, hence ax2+by2ax^2+by^2 takes at most 3×2=63\times2=6 different remainders. If both aa and bb are odd, then ax2+by2≡x2±y2(mod4)ax^2+by^2\equiv x^2\pm y^2 \pmod 4; the expression x2+y2x^2+y^2 does not take the remainder 3 modulo 4 and x2−y2x^2-y^2 does not take the remainder 2 modulo 4.

Consider the case when p≥3p\ge3. The ppth powers take exactly pp different remainders modulo p2p^2. Indeed, (x+kp)p(x+kp)^p and xpx^p have the same remainder modulo p2p^2, and all numbers 0p0^p, 1p1^p, …\dots, (p−1)p(p-1)^p are different even modulo pp. So, axp+bypax^p+by^p take at most p2p^2 different remainders modulo p2p^2. If it takes strictly less then p2p^2 different remainders modulo p2p^2, we get infinitely many non-representable numbers. If it takes exactly p2p^2 remainders, then axp+bypax^p+by^p is divisible by p2p^2 only if both xx and yy are divisible by pp. Hence if axp+bypax^p+by^p is divisible by p2p^2, it is also divisible by ppp^p. Again we get infinitely many non-representable numbers, for example the numbers congruent to p2p^2 modulo p3p^3 are non-representable.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 3. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;