$p\mid n \implies p^2-1 \mid n$

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

$p\mid n \implies p^2-1 \mid n$

Messaggio da jordan » 04 nov 2012, 12:27

Trovare il piu' grande intero positivo $n$ minore di $2012$ tali che se un primo $p$ divide $n$, allora anche $p^2-1$ divide $n$.


(Cono Sur Olympiad 2012)

[Edit: corretta la parte in rosso]
Ultima modifica di jordan il 04 nov 2012, 15:11, modificato 1 volta in totale.
The only goal of science is the honor of the human spirit.

nic.h.97
Messaggi: 195
Iscritto il: 19 giu 2012, 19:24

Re: $p\mid n \implies p^2-1 \mid n$

Messaggio da nic.h.97 » 04 nov 2012, 13:46

n= 1320 , i multipli di 336 , i multipli di 120 , i multipli di 6 , i multipli di 24.
Probabilmente sto sbagliando...

Avatar utente
razorbeard
Messaggi: 116
Iscritto il: 20 apr 2011, 16:28

Re: $p\mid n \implies p^2-1 \mid n$

Messaggio da razorbeard » 04 nov 2012, 14:13

1320 è diviso da 61, ma non da $61^2-1$
E' un buon giorno... per morire

nic.h.97
Messaggi: 195
Iscritto il: 19 giu 2012, 19:24

Re: $p\mid n \implies p^2-1 \mid n$

Messaggio da nic.h.97 » 04 nov 2012, 14:23

1320 è diviso da 11e da 11^2-1

Avatar utente
razorbeard
Messaggi: 116
Iscritto il: 20 apr 2011, 16:28

Re: $p\mid n \implies p^2-1 \mid n$

Messaggio da razorbeard » 04 nov 2012, 14:30

Questo è vero ma l'esercizio dice che se un primo divide $n$ allora anche $p^2-1$ divide $n$, per ogni primo che divide $n$.
E' un buon giorno... per morire

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: $p\mid n \implies p^2-1 \mid n$

Messaggio da jordan » 04 nov 2012, 14:49

[Testo editato]
Ultima modifica di jordan il 04 nov 2012, 15:12, modificato 1 volta in totale.
The only goal of science is the honor of the human spirit.

Avatar utente
razorbeard
Messaggi: 116
Iscritto il: 20 apr 2011, 16:28

Re: $p\mid n \implies p^2-1 \mid n$

Messaggio da razorbeard » 04 nov 2012, 14:52

Secondo me sono tutti i numeri della forma:
$2^a \cdot 3^b$ con $a \geq 3$
$2^a \cdot 3^b \cdot 5^c$ con $a \geq 3$
$2^a \cdot 3^b \cdot 5^c \cdot 7^d$ con $a \geq 4$
Poi i conti si fanno tenendo conto della limitazione $n<2012$.
Dimenticavo: $a,b,c,d$ sono interi positivi.
E' un buon giorno... per morire

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: $p\mid n \implies p^2-1 \mid n$

Messaggio da jordan » 04 nov 2012, 14:57

[Editato commento errato sulle fattorizzazioni $p^2-1$ : il ragionamento sotto di razorbeard è corretto, resta da trovare quale è l'intero positivo piu' grande che soddisfa tale proprietà..]
Ultima modifica di jordan il 04 nov 2012, 15:15, modificato 1 volta in totale.
The only goal of science is the honor of the human spirit.

Avatar utente
razorbeard
Messaggi: 116
Iscritto il: 20 apr 2011, 16:28

Re: $p\mid n \implies p^2-1 \mid n$

Messaggio da razorbeard » 04 nov 2012, 15:05

Non ho capito cosa intendi...posso spiegare come ho ragionato:
dato che almeno uno fra $p,p-1,p+1$ è pari allora sicuramente $2|n$, da qui si deduce che $6|n$, allora sicuramente $12|n$.
Dato che ho analizzato la situazione in cui 2 e 3 dividono $n$ allora posso metterli nella fattorizzazione quante volte voglio,dato che sono sicuro che $2^2-1$ e $3^2-1$ dividono $n$.
Ora metto dentro anche il 5,devo essere sicuro che però $24|n$ per cui devo sistemare gli esponenti di 2 e 3.
Stesso ragionamento con 7...poi mi accorgo che non posso salire piuù di tanto perchè $n<2012$
Detto ciò chiedo chiarimenti sulle fattorizzazioni di cui parlavi prima.
E' un buon giorno... per morire

toti96
Messaggi: 53
Iscritto il: 02 nov 2012, 20:17

Re: $p\mid n \implies p^2-1 \mid n$

Messaggio da toti96 » 04 nov 2012, 15:25

provo a dimostrare che sono tutti i numeri della forma $ 24m $ con m maggiore o uguale a 1 e minore o uguale a 83. allora io ho analizzato i primi cominciando dal caso particolare $ p=2 $,che ci porta a $ 3 $ divisore di $ n $ che ci porta a sua volta a $ 24 $ divisore di $ n $. lasciando da parte quindi 2 (che porta all'analisi anche di 3) tutti i numeri dispari sono esprimibili come :$ 3m o 3m+1 o 3m+2 $. tralasciamo $ 3m $ che non ci dà primi (a parte il caso 3 già visto) $ 3m+1 $ è dispari se e solo se $ m=2k $. ora sostituiamo e consideriamo $ p^2-1=(p+1)(p-1) $ che si trasforma in $ 6k(6k+2) $. ora distinguiamo a sua volta due possibilità per k $ k=2a $ che si trasforma in$ 24a(6a+1) $ uguale alla tesi in questo particolare caso. con $ k=2a+1 $ si trasforma in $ 24(2a+1)(3a+2) $. anche qui la tesi è dimostrata passiamo al caso $ p=3m+2 $ che per essere dispari deve avere$ m=2k+1 $ e che quindi si trasforma in $ (p+1)(p-1)=(6k+4)(6k+6) $ svolgiamo esce$ 36k^2+60k+24 $ che è multiplo di 24 se e solo se $ 36k^2+60k=12k(3k+5) $ lo è. analizziamo il caso $ k=2a $ che ci porta a $ 24a(6a+5) $ sempre divisibile per 24 . nel caso $ k=2a+1 $ allora sostituiamo ed esce $ 24(2a+1)(3a+4) $ sempre divisibile per 24. ora quello che mi trovo dimostrato è in realtà che qualsiasi numero dispari della forma $ 3m+1 o 3m+2 $ ha il prodotto del suo antecedente e del suo successore naturale multiplo di 24 . il che varrà allora anche per i p primi sottoinsieme dei dispari così esprimibili e quindi qualsiasi numero divisibile per $ p $ e per$ p^2-1 $ è un 24m quindi il più grande intero è $ 24 *83=1992 $
Ultima modifica di toti96 il 04 nov 2012, 15:43, modificato 2 volte in totale.

Avatar utente
razorbeard
Messaggi: 116
Iscritto il: 20 apr 2011, 16:28

Re: $p\mid n \implies p^2-1 \mid n$

Messaggio da razorbeard » 04 nov 2012, 15:26

Per quanto riguarda il più grande numero, si può seguire il ragionamento del messaggio precedente...
constatando che i multipli di 12 vanno bene tutti si può andare avanti di 12 in 12 finchè non si arriva il più vicino possibile a 2012, e il valore cercato è 2004.
Spero che la risposta sia esatta,perchè devo festeggiare in qualche modo il 100° messaggio :D
E' un buon giorno... per morire

toti96
Messaggi: 53
Iscritto il: 02 nov 2012, 20:17

Re: $p\mid n \implies p^2-1 \mid n$

Messaggio da toti96 » 04 nov 2012, 15:31

ma non tutti i multipli di 12 vanno bene ad esempio 36 è divisibile per $ 2 $ e $ 2^2-1 $ , per $ 3 $ ma non per$ 3^2-1=8 $ che non divide 36

Avatar utente
razorbeard
Messaggi: 116
Iscritto il: 20 apr 2011, 16:28

Re: $p\mid n \implies p^2-1 \mid n$

Messaggio da razorbeard » 04 nov 2012, 15:35

E' vero,ho commesso un maledetto errore di distrazione,volevo dire che tutti i multipli di 24 vanno bene,come ho scitto nel primo punto di 2 messaggi fa,non di 12.
Correggendo questa svista il valore cercato dovrebbe essere 1992 :P
E' un buon giorno... per morire

toti96
Messaggi: 53
Iscritto il: 02 nov 2012, 20:17

Re: $p\mid n \implies p^2-1 \mid n$

Messaggio da toti96 » 04 nov 2012, 15:36

credo anche io sia così ... :P

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: $p\mid n \implies p^2-1 \mid n$

Messaggio da jordan » 04 nov 2012, 15:42

$1992$ avrà anche qualche altro fattore primo..
The only goal of science is the honor of the human spirit.

Rispondi