Mod

2nisic · #1

Έστω

θετική ακέραιοι και έστω $p=2^{2^{m}}+1$ με

πρώτο να αποδειχθεί ότι:

$2^{2^{m+1}p^{k}}\equiv 1$ (modp^(k+1))

Και πώς ο $2^{m+1}p^{k}}$ είναι μικρότερος

για τον οποίο ισχύει: $2^{n}\equiv 1$ (modp^(k+1))

ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ · #2

2nisic έγραψε: ↑
Δευ Ιαν 25, 2021 12:28 pm
Έστω θετική ακέραιοι και έστω $p=2^{2^{m}}+1$ με πρώτο να αποδειχθεί ότι:

$2^{2^{m+1}p^{k}}\equiv 1$ (modp^(k+1))

Και πώς ο $2^{m+1}p^{k}}$ είναι μικρότερος για τον οποίο ισχύει: $2^{n}\equiv 1$ (modp^(k+1))

Είναι $2^{2^{m+1}p^k}-1=(2^{2^m})^{2p^k}-1=((p-1)^{p^k}-1)((p-1)^{p^k}+1)$
Αρκεί λοιπόν $p^k|(p-1)^{p^k}+1$ το οποίο προκύπτει από LTE

αφού

έτσι $u_p((p-1)^{p^k}+1)=u_p(p)+u_p(p^k)=k+1$
Έστω τώρα t=ord_p(2)

και

ο μικρότερος με $2^n=1\pmod p^{k+1}$ .
Είναι p|2^n-1

άρα

. Επιπλέον $p|p(2^{2^{m}}-1)=2^{2^{m+1}}-1$ αλλά $p\not |p-1=2^{2^{m}}-1$ έτσι $t|2^{m+1}$ αλλά $t\not |2^m$ που σημαίνει $t=2^{m+1}$ άρα $2^{m+1}|n$
Επίσης αν γράψω $2^{2^{m+1}p^k}=en+q,0\leq q<n$ τότε προκύπτει $p^{k+1}|2^q-1$ άρα πρέπει q=0

δηλαδή $n|2^{m+1}p^k$ .
Έτσι λοιπόν γράφω $n=2^{m+1}p^l$ και υποθέτοντας ότι δεν ισχύει το ζητούμενο θεωρούμε l<k

Είναι $2^n-1=(2^{2^{m}p^l}-1)(2^{2^{m}p^l}+1)$ και $p\not | (2^{2^{m}p^l}-1)\equiv -2\pmod p$
Άρα $u_p(2^n-1)=u_p(2^{2^{m}p^l}+1)=u_p(p)+u_p(p^l)=1+l<1+k$ άτοπο!
Το ζητούμενο έπεται.

2nisic · #3

Joaakim · #4

Το Πρόβλημα προέρχεται από Διαγωνισμό στην Κίνα το 2010.
https://artofproblemsolving.com/communi ... 22p2068187

Mod

Mod

Re: Mod

Re: Mod

Re: Mod

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