IMC 2024, Ημέρα 2, Θέμα 10
We say that a square-free positive integer is almost prime if
for all integers , where are all the positive divisors of . Suppose that is a Fermat prime (i.e. it is a prime of the form for an integer ), is a prime divisor of an almost prime integer , and . Show that, with the above notation, for all .
(An integer is called square-free if it is not divisible by for any integer .)
Πρωτότυπο από το επίσημο PDF

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.
Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.
Επίσημη λύση
(proposed by Tigran Hakobyan, Yerevan State University, Vanadzor, Armenia)
Solution. We first prove the following claims.
Lemma 1. If is almost prime then .
Proof. Assume to the contrary that so that there are primes and dividing such that . For let be the number of positive divisors of congruent to modulo and similarly for let denote the number of positive divisors of congruent to modulo . Observe that the polynomial defines the zero function on due to the condition of the problem. On the other hand, in , so that for all . It follows that which is a contradiction (here means the number of distinct prime divisors of ). Therefore our assumption was wrong and the lemma is proved.
Lemma 2. Let be a prime number and let be a positive integer coprime to . If is the order of modulo , then there exists such that and
Proof. Observe that for any since . On the other hand, the numbers leave different remainders upon division by and therefore the polynomial
Lemma 3. If is almost prime then for any primes and dividing , the order of modulo is an odd number.
Proof. Observe that due to Lemma 1 the order of modulo is well defined and assume to the contrary that is an even number. According to Lemma 2 there exists such that and , where . Let us consider the sequence defined by and for . Notice that since is even by the assumption, we have . It follows that
Let us get back to the problem. Suppose that is prime and is a Fermat's prime such that . If is any prime divisor of , then by Lemma 3 we have that for some odd , so that and therefore . Hence for any divisor of .
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 5–6. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.
Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.
Πώς πήγε;
Οι κινήσεις που σημειώνεις επιστρέφουν νωρίτερα στη διαλογή.