3 numeri primi

[David]

Siano p, q e r 3 numeri primi e n un numero naturale legati dalle relazioni:

$\Large\{ p\cdot r^3\,\equiv\, n\; \pmod { n\cdot r} \\ q\cdot(1+r)=r^2+111111$

trovare p,q,r in modo che p+q+r sia minima.

Bye David

[fabtor]

Siano p, q e r 3 numeri primi e n un numero naturale legati dalle relazioni:

$\Large\{ p\cdot r^3\,\equiv\, n\; \pmod { n\cdot r} \\ q\cdot(1+r)=r^2+111111$

trovare p,q,r in modo che p+q+r sia minima.

Bye David

Sei una fucina di quesiti caro david... e tutti non banali!!! ci ragionerò sopra apena posso anche se il calcolo modulare (avendolo imparato da autodidatta) non l'ho mai del tutto digerito.

[David]

Caro fabtor ti ringrazio per il sostegno, anche se devo dire in tutta onestà che la mia mente trova sempre più difficile partorire problemi creativi e ricreativi di una certa frizzantezza, rompicapo che si reggano su un certo equilibrio strutturale non dovendo scadere nella banalità o nel dejà-vu da una parte e non rasentando questioni tecnicamente troppo difficili (soprattutto per me!) dall'altra.
In fondo il bello di questo stupendo forum è che tutti possiamo dare il nostro piccolo o grande contributo senza dover far le gare per la palma di miglior matematico e senza doverci preoccupare se ogni tanto estrapoliamo dal cilindro qualche strafalcione.
Se affrontata con tale spirito ludico, sono convinto che molti potrebbero ricredersi su di essa e trovare nella matematica uno squisito e avvincente passatempo. ( Come insegnava il compianto nonchè mitico Martin Gardner)
Quindi se anche solo una persona ritenesse appassionante un problema da me posto, potrei considerarmi già appagato,poichè significa che quella piccola idea che ti è balenata in mente chissà quando, chissa come, viene apprezzata da qualcuno e suscita uno stimolo a ripercorrerla, magari attraverso altre vie che tu non avevi scorto e che ti possono portare a nuovi e magnifici eden matematici.
Dunque grazie a te caro fabtor anche stavolta mi sono guadagnato la pagnotta..

Bye David

[Pasquale]

Pardon David, chiariscimi la simbologia: quando scrivi n(Mod n*r), intendi n modulo n*r, ovvero il resto della divisione fra n ed n*r , cioè fra 1 ed r, quindi 1?

[David]

La prima relazione posso scriverla:

$pr^3=knr+n$

[Pasquale]

Senza l’ausilio del pc non so farlo e se non ho fatto errori, scartati i valori non primi, quelli che ci interessano sono:

p = 907
q = 881
r = 151

talché:

p + q + r = 1939


In prima battuta, ho esaminato la relazione:

$r = \frac{r^2+111111}{q} - 1$ , da cui : q = 881; r = 151


Quindi sono passato alla risoluzione di:

$p = \frac{n}{r^3}(kr+1)$, in cui non essendo (kr + 1) divisibile per $r^3$, deve esserlo n, se vogliamo p intero.

Per cui, considerato il valore minimo richiesto dal testo, assumendo $n = r^3$, si trova che, per k = 6, p = 907

Non ho trovato primi più piccoli che soddisfino le due equazioni e pertanto ritengo che non vi sia una somma p+q+r < 1939.

Minimi i tempi di elaborazione, utilizzando 3 algoritmi diversi nelle varie fasi della ricerca (un pochino di più con un solo algoritmo più bello da vedere).

[panurgo]

Senza l’ausilio del pc non so farlo e se non ho fatto errori, scartati i valori non primi, quelli che ci interessano sono:

p = 907
q = 881
r = 151

$\left\{ \begin{array}{l} p\/r^{\script 3}\/\equiv\/n\;\pmod{n\/r}\\ q\/\left(r\/+\/1\right)\/=\/r^{\script 2}\/+\/111111\\ \end{array} \right\.$

Vediamo cosa è possibile dedurre dalla seconda equazione (senza l'ausilio del computer)

$q\/\left(r\/+\/1\right)\/=\/r^{\script 2}\/+\/111111$

In primo luogo $r\/\neq\/2$ perché

$r\/=\/2\qquad\Longrightarrow\qquad 3q\/=\/111115$

e

$111115\/\equiv\/1\;\pmod{3}$

con la conseguenza che $q$ non può essere intero; inoltre $q\/\neq\/2$ perché i numeri in questione sono troppo grandi.
Poi, se esprimiamo $r^{\script 2}$ come

$r^{\script 2}\/=\/\left(r\/-\/1\right)\/\left(r\/+\/1\right)\/+\/1$

abbiamo

$\left(q\/-\/r\/+\/1\right)\/\left(r\/+\/1\right)\/=\/111112$

e cioè $111112\/\equiv\/0\;\pmod{r\/+\/1}$ ($r\/+\/1$ deve essere un divisore di $111112$).
Dato che $q\/-\/r\/+\/1$ è dispari e $111112$ si fattorizza come $8\/\times\/17\/\times\/19\/\times\/43$, $r\/+\/1$ deve essere un multiplo di $8$: i divisori di $111112$ che sono multipli di $8$ sono $136$, $152$, $344$, $2584$, $5848$ e $6536$.
Sottraendo $1$ da ciascuno di essi si trova $135$, $151$, $343$, $2583$, $5847$ e $6535$: di questi solo $151$ è primo per cui $r\/=\/151$ e $q\/=\/881$.
Passiamo ora alla prima.
Effettivamente $kr\/+\/1$ non è divisibile per $r^{\script 3}$ perché

$kr\/\equiv\/0\;\pmod{r^{\script 3}}\qquad\Longrightarrow\qquad k\/=\/hr^{\script 2}$

per qualunque altro valore di $k$ il resto della divisione varia tra $r$ e $r^{\script 3}\/-\/r$.
Come arguisce bene Pasquale, deve essere $n\/=\/r^{\script3}$ e $p\/=\/151k\/+\/1$; ovviamente è $p\/\neq\/2$, quindi deve essere dispari e $k$ pari: proviamo (senza ausilio del computer, ho una tavola di numeri primi) i primi valori $k$, $2$, $4$ e $6$ cui corrispondo $303$, $605$ e $907$ che è primo...

[Pasquale]

Qualcosa di quanto detto (tipo l'esclusione del 2, oltre un test di primalità) pure l'ho dovuta suggerire al p.c., perché non è che fa tutto da solo, ma resta il fatto che Panurgo è Panurgo ed ha sempre qualcosa di bello da farci vedere. Ciao Pan, è sempre un piacere leggerti.

[David]

Ottimo boys i nostri 3 piccoli amici sono proprio loro.

Come mi piace Guido quel "senza l'ausilio del computer"!

Effettivamente, l'operazione di maquillage stava tutta in quella scomposizione di 111112,dopodichè strada spianata!

Bye David