Putnam 2015/A5

#1

Έστω περιττός ακέραιος

. Συμβολίζουμε με N_q

τον αριθμό των ακεραίων

με

οι οποίοι σχετικά πρώτοι με τον

. Να δειχθεί ότι το N_q

είναι περιττό αν και μόνο αν ο

είναι της μορφής p^k

όπου

θετικός ακέραιος και

πρώτος της μορφής $5 \bmod 8$ ή $7 \bmod 8$ .

Mikesar · #2

Ας κάνω μια προσπάθεια. Η βασική ιδέα της απόδειξης είναι ίδια με την απόδειξη για τον τύπο της $\phi(n)$ .
Έστω $\displaystyle q=p_{1}^{a_1}\cdot...\cdot p_{n}^{a_n}$ και A_i

το σύνολο των ακεραίων από

έως

που διαιρούνται από p_i

. Από την αρχή εγκλεισμού αποκλεισμού:
$N_q=\displaystyle \sum_{I\subset[n]}(-1)^{|I|}|\bigcap_{i\in I}A_i|=\displaystyle \sum_{I\subset[n]}(-1)^{|I|}\left\lfloor{\frac{q}{4\prod_{i\in I}p_i}}\right\rfloor$ .
Θέλουμε να μελετήσουμε την παράσταση αυτή $mod\ 2$ . Τα ακέραια μέρη στο παραπάνω άθροισμα θα εξαρτώνται από την τιμή του αριθμητή $mod\ 8$ . Συγκεκριμένα, $\displaystyle\frac{8k+1}{4},\ \frac{8k+3}{4}\equiv0 \ (mod\ 2)$ και $\displaystyle\frac{8k+5}{4},\ \frac{8k+7}{4}\equiv1 \ (mod\ 2)$ . Επίσης $\displaystyle p_i^2\equiv1\ (mod\ 8)\Rightarrow \frac{q}{P_I}\equiv qP_I\ (mod\ 8)$ , όπου $P_I=\prod_{i\in I}p_i.$ Συνοψίζοντας,
$\displaystyle N_q\equiv \sum_{I\subset[n]}\left\lfloor{\frac{qP_I}{4}}\right\rfloor\ (mod\ 2)$
Θέλουμε να δείξουμε ότι αν $n\geq2$ το δεξί μέλος είναι 0. Αυτό μας παρακινεί να ζευγαρώσουμε τους όρους του αθροίσματος ανά τέσσερεις. Γράφουμε το δεξί μέλος ως
$\displaystyle\sum_{I\subset[n]\backslash\{1,2\}}\left\lfloor{\frac{qP_I}{4}}\right\rfloor+\left\lfloor{\frac{qp_1P_I}{4}}\right\rfloor+\left\lfloor{\frac{qp_2P_I}{4}}\right\rfloor+\left\lfloor{\frac{qp_1p_2P_I}{4}}\right\rfloor \ (mod\ 2)$
Ισχυρίζομαι ότι από τους τέσσερεις αριθμητές άρτιο πλήθος είναι

ή

$(mod \ 8)$ .
Αν $1\not\equiv p_1\not\equiv p_2\not\equiv 1\ (mod\ 8)$ τότε οι τέσσερεις αριθμητές είναι περιττοί και ανά δύο διαφορετικοί $(mod\ 8)$ .
Αν ΧΒΓ $p_1\equiv1 \ (mod\ 8)$ τότε οι αριθμητές γίνονται qP_I,qP_I,qp_2P_I,qp_2P_I

.
Αν $p_1\equiv p_2\ (mod\ 8)$ τότε οι αριθμητές γίνονται qP_I,qp_1P_I,qp_1P_I,qP_I

.
Έτσι ο ισχυρισμός μου είναι αληθής. Άρα n=1

. Η μελέτη αυτής της περίπτωσης είναι εύκολη και δίνει το ζητούμενο.

Putnam 2015/A5

Putnam 2015/A5

Re: Putnam 2015/A5

Μέλη σε σύνδεση