uniolympiads English

IMC 2011, Ημέρα 1, Θέμα 3

Let pp be a prime number. Call a positive integer nn interesting if

xn−1=(xp−x+1)f(x)+pg(x)x^n - 1 = (x^p - x + 1)f(x) + pg(x)

for some polynomials ff and gg with integer coefficients.

a) Prove that the number pp−1p^p - 1 is interesting.

b) For which pp is pp−1p^p - 1 the minimal interesting number?

Eugene Goryachko and Fedor Petrov, St. Petersburg

Πρωτότυπο από το επίσημο PDFLet p be a prime number. Call a positive integer n interesting if x n − 1 = (x p − x + 1)f (x) + pg(x) for some polynomials f and g with integer coefficients. a) Prove that the number p p − 1 is interesting. b) For which p is p p − 1 the minimal interesting number? (Eugene Goryachko and Fedor Petrov, St. Petersburg)

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

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

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

Επίσημη λύση

(Eugene Goryachko and Fedor Petrov, St. Petersburg)

Solution. (a) Let's reformulate the property of being interesting: nn is interesting if xn−1x^n-1 is divisible by xp−x+1x^p-x+1 in the ring of polynomials over Fp\mathbb F_p (the field of residues modulo pp). All further congruences are modulo xp−x+1x^p-x+1 in this ring. We have xp≡x−1x^p\equiv x-1, then xp2=(xp)p≡(x−1)p≡xp−1≡x−2x^{p^2}=(x^p)^p\equiv(x-1)^p\equiv x^p-1\equiv x-2, xp3=(xp2)p≡(x−2)p≡xp−2p≡x−2p−1≡x−3x^{p^3}=(x^{p^2})^p\equiv(x-2)^p\equiv x^p-2^p\equiv x-2^p-1\equiv x-3 and so on by Fermat's little theorem, finally xpp≡x−p≡xx^{p^p}\equiv x-p\equiv x,

x(xpp−1−1)≡0.x(x^{p^p-1}-1)\equiv0.
Since the polynomials xp−x+1x^p-x+1 and xx are coprime, this implies xpp−1−1≡0x^{p^p-1}-1\equiv0.

(b) We write

x1+p+p2+⋯+pp−1=x⋅xp⋅xp2⋅…⋅xpp−1≡x(x−1)(x−2)…(x−(p−1))=xp−x≡−1,x^{1+p+p^2+\dots+p^{p-1}}=x\cdot x^p\cdot x^{p^2}\cdot\ldots\cdot x^{p^{p-1}}\equiv x(x-1)(x-2)\ldots(x-(p-1))=x^p-x\equiv-1,
hence x2(1+p+p2+⋯+pp−1)≡1x^{2(1+p+p^2+\dots+p^{p-1})}\equiv1 and a=2(1+p+p2+⋯+pp−1)a=2(1+p+p^2+\dots+p^{p-1}) is an interesting number.

If p>3p>3, then a=2p−1(pp−1)<pp−1a=\frac{2}{p-1}(p^p-1)<p^p-1, so we have an interesting number less than pp−1p^p-1. On the other hand, we show that p=2p=2 and p=3p=3 do satisfy the condition. First notice that by gcd(xm−1,xk−1)=xgcd(m,k)−1gcd(x^m-1,x^k-1)=x^{gcd(m,k)}-1, for every fixed pp the greatest common divisors of interesting numbers is also an interesting number. Therefore the minimal interesting number divides all interesting numbers. In particular, the minimal interesting number is a divisor of pp−1p^p-1.

For p=2p=2 we have pp−1=3p^p-1=3, so the minimal interesting number is 11 or 33. But x2−x+1x^2-x+1 does not divide x−1x-1, so 11 is not interesting. Then the minimal interesting number is 33.

For p=3p=3 we have pp−1=26p^p-1=26 whose divisors are 1,2,13,261,2,13,26. The numbers 11 and 22 are too small and x13≡−1≢+1x^{13}\equiv-1\not\equiv+1 as shown above, so none of 11,22 and 1313 is interesting. So 2626 is the minimal interesting number.

Hence, pp−1p^p-1 is the minimal interesting number if and only if p=2p=2 or p=3p=3.

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

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

Πώς πήγε;