Vojtech Jarvik 2016/2 Category I

Συντονιστής: Demetres

Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8113
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Vojtech Jarvik 2016/2 Category I

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Σάβ Απρ 23, 2016 5:36 pm

Να βρεθούν όλοι οι θετικοί ακέραιοι n ώστε το \varphi(n) να διαιρεί το n^2+3.


simantiris j.
Δημοσιεύσεις: 247
Εγγραφή: Σάβ Ιαν 18, 2014 5:07 pm

Re: Vojtech Jarvik 2016/2 Category I

#2

Μη αναγνωσμένη δημοσίευση από simantiris j. » Παρ Σεπ 01, 2017 9:17 pm

Καλησπέρα :logo: !Ωραίο αλλά δύσκολο πρόβλημα,με αρκετή περιπτωσιολογία.Βάζω εδώ τη λύση μου.
Προφανώς τα n=1,2 είναι λύσεις.Έστω τώρα n>2 τέτοιος φυσικός.Από θεώρημα Euler είναι a^{n^2+3}\equiv a^{k\varphi (n)}\equiv 1(modn),\forall a με (a,n)=1.Επιλέγοντας a=n-1 είναι (-1)^{n^2+3}\equiv 1 (modn) άρα (αφού n\neq 2) ο n είναι περιττός,άρα n^2+3\equiv 4(mod8).
Όμως αν n=p_{1}^{a_{1}}...p_{k}^{a_{k}} η παραγοντοποίηση του n σε πρώτους,τότε,αφού \varphi (n)=p_{1}^{a_{1}-1}...p_{k}^{a_{k}-1}(p_{1}-1)...(p_{k}-1) είναι 2^k /\varphi (n) άρα για k\geq 3,8/\varphi (n)/n^2+3,άτοπο.Συνεπώς k\leq 2.
Αν k=1 τότε n=p^{a}.Αν a>1 τότε p^a-p^{a-1}/p^{2a}+3\Rightarrow p^{a-1}/3.Άρα p=3,a=2\Rightarrow n=9 που είναι λύση.Αν πάλι a=1 τότε p-1/p^2+3\Rightarrow p-1/4\Rightarrow n=p=5 ή n=p=3 που είναι λύσεις.
Έστω τώρα k=2 και ότι a_{1}=a_{2}=1 δηλαδή για ευκολία n=pq με p,q πρώτους.
Αυτή η περίπτωση είναι το δύσκολο κομμάτι της άσκησης.Είναι (p-1)(q-1)/p^2q^2+3Αν (χωρίς βλάβη της γενικότητας) 3/p-1 τότε 3/(p-1)(q-1)/p^2q^2+3\Rightarrow 3/q\Rightarrow q=3 και προκύπτει ότι p=7 άρα n=21 που είναι λύση.Αλλιώς πρέπει p\equiv q\equiv 2(mod3).Έστω p=2k+1,q=2m+1 (παρατηρούμε ότι επίσης k\equiv m\equiv 2(mod3)) και έχουμε ότι 4km/((2k+1)(2m+1))^2+3\Rightarrow 4km/4k^2+4m^2+4+8km+4k+4m\Rightarrow km/k^2+m^2+k+m+1\Rightarrow km/(k+m)^2+(k+m)+1.
Ο k τώρα (εύκολα με απαγωγή σε άτοπο) έχει πρώτο διαιρέτη s=3t+2
.Τότε ανu=k+m είναιu^2+u+1\equiv 0(mod s)\Rightarrow u^3\equiv 1(mod s)\Rightarrow u^{3t}\equiv 1(mod s).
Όμως από θεώρημα Fermat (ανs/u\Rightarrow s/1,άτοπο,άρα (u,s)=1)

είναι u^{s-1}\equiv 1(mod s)\Rightarrow u^{3t+1}\equiv 1\Rightarrow u^{3t}u\equiv 1(mod s)\Rightarrow u\equiv 1(mod s).Τότε είναιu^2+u+1\equiv 3\equiv 0(mod s)\Rightarrow s=3,άτοπο.Άρα δεν έχουμε λύσεις σε αυτή την περίπτωση.
Τέλος,έστω a_{1}=max{a_{1},a_{2}}\geq 2.Τότε p_{1}^{a_{1}-1}p_{2}^{a_{2}-1}(p_{1}-1)(p_{2}-1)/p_{1}^{2a_{1}}p_{2}^{2a_{2}}+3\Rightarrow p_{1}^{a_{1}-1}/3\Rightarrow p_{1}=3,a_{1}=2 άρα a_{2}\leq 2(τώρα γίνεται αντιληπτό ότι αν a_{2}=max{a_{1},a_{2}}\geq 2 θα ήταν p_{2}=3>p_{1},άτοπο).
Μένουν λοιπόν οι 2 περιπτώσεις a_{2}=1,a_{2}=2 που εύκολα διαπιστώνουμε ότι δε δίνουν λύσεις.
Τελικά n\in {1,2,3,5,9,21}


Σημαντήρης Γιάννης
Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 2 επισκέπτες