Può essere?

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
Bruno
Livello 9
Livello 9
Messaggi: 1431
Iscritto il: lun nov 21, 2005 6:07 pm
Località: Bologna

Può essere?

Messaggio da Bruno »

I seguenti numeri possono essere primi?

a) $\;3^{535}-10$
b) $\;6^{123}-7$
c) $\;7^{345}-2$

Perché?
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
(Biagio Marin)

panurgo
Livello 9
Livello 9
Messaggi: 1323
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: Può essere?

Messaggio da panurgo »

Comincio da $\text{c)}$: dato che

$\displaystyle 7\equiv 2\;\left(\text{mod}\;5\right)$

segue che

$\displaystyle 7^{345}\equiv 2^{345}\;\left(\text{mod}\;5\right)$

La cifra delle unità delle potenze di due è $2,\ 4,\ 8,\ 6,\ 2,\ldots$, ovvero è $2$ per le potenze di due della forma $4k+1$: da tutto ciò segue che


$\displaystyle 7^{345} - 2\equiv 2^{345} - 2\equiv 0\;\left(\text{mod}\;5\right)$

cioè $7^{345} - 2$ è divisibile per $5$
il panurgo

Principio di Relatività: {\bb m} \not \right {\bb M} \ \Longleftrightarrow \ {\bb M} \not \right {\bb m}
"Se la montagna non va a Maometto, Maometto NON va alla montagna"

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1176
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Può essere?

Messaggio da Gianfranco »

Bruno ha scritto:
gio ago 27, 2020 5:55 pm
I seguenti numeri possono essere primi?
b) $\;6^{123}-7$
Perché?
La domanda è se i numeri dati "possono" (o "potrebbero"?) essere numeri primi.

Il numero $\;6^{123}-7$ potrebbe essere primo perché è del tipo $6n-1$
Anche il numero $\;3^{535}-10$.

Ma probabilmente nessuno dei due numeri è primo.
Pace e bene a tutti.
Gianfranco

panurgo
Livello 9
Livello 9
Messaggi: 1323
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: Può essere?

Messaggio da panurgo »

$\displaystyle \text{a)}$

Dimostriamo che $3^{535}-10\propto 7$: infatti

$\displaystyle 10\equiv 3\quad\left(\text{mod}\;7\right)$

quindi

$\displaystyle 3^{535}-10\equiv 3\left(3^{534}-1\right)\quad\left(\text{mod}\;7\right)$

e non ci resta che dimostrare che

$\displaystyle 3^{534}\equiv 1\quad\left(\text{mod}\;7\right)$

Osserviamo i resti modulo sette delle potenze di $3$

$\left. \begin{array}{lC}
3^1\equiv 3 \\
3^2\equiv 3\times 3^1\equiv 9\equiv 2 \\
3^3\equiv 3\times 3^2\equiv 6 \\
3^4\equiv 3\times 3^3\equiv 18\equiv 4 \\
3^5\equiv 3\times 3^4\equiv 12\equiv 5 \\
3^6\equiv 3\times 3^5\equiv 15\equiv 1 \\
3^3\equiv 3\times 3^6\equiv 3 \\
\vdots \\
\end{array}\right\} \qquad \left(\text{mod}\;7\right)$

e ricaviamo che

$\displaystyle 3^{6k}\equiv 1\quad\left(\text{mod}\;7\right)$

Poiché $534=6\times 89$ segue la tesi.

$\displaystyle \text{b)}$

Osserviamo i resti modulo undici delle potenze di $6$

$\left.\begin{array}{lC}
6^1\equiv 6 \\
6^2\equiv 6\times 6^1\equiv 36\equiv 3 \\
6^3\equiv 6\times 6^2\equiv 18\equiv 7 \\
6^4\equiv 6\times 6^3\equiv 42\equiv 9 \\
6^5\equiv 6\times 6^4\equiv 54\equiv 10 \\
6^6\equiv 6\times 6^5\equiv 60\equiv 5 \\
6^7\equiv 6\times 6^6\equiv 30\equiv 8 \\
6^8\equiv 6\times 6^7\equiv 48\equiv 4 \\
6^9\equiv 6\times 6^8\equiv 24\equiv 2 \\
6^{10}\equiv 6\times 6^9\equiv 12\equiv 1 \\
6^{11}\equiv 6\times 6^{10}\equiv 6 \\
\vdots \\
\end{array}\right\}\qquad \left(\text{mod}\;11\right)$

e ricaviamo che

$\displaystyle 6^{10k+3}\equiv 7\quad\left(\text{mod}\;11\right)$

quindi $6^{123}-7\propto 11$.
il panurgo

Principio di Relatività: {\bb m} \not \right {\bb M} \ \Longleftrightarrow \ {\bb M} \not \right {\bb m}
"Se la montagna non va a Maometto, Maometto NON va alla montagna"

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1176
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Può essere?

Messaggio da Gianfranco »

Prima di tutto, applausi a Panurgo...
picard_clapping.gif
picard_clapping.gif (151.89 KiB) Visto 228 volte
Poi la mia modesta dimostrazione che $6^{123}-7$ è divisibile per 11.

mod11.png
mod11.png (15.68 KiB) Visto 228 volte
Pace e bene a tutti.
Gianfranco

Bruno
Livello 9
Livello 9
Messaggi: 1431
Iscritto il: lun nov 21, 2005 6:07 pm
Località: Bologna

Re: Può essere?

Messaggio da Bruno »

Eccomi qui :D

Molto bene.


Gianfranco ha scritto:
sab ago 29, 2020 11:30 am

La domanda è se i numeri dati "possono" (o "potrebbero"?) essere numeri primi.

Il numero $\;6^{123}-7$ potrebbe essere primo perché è del tipo $6n-1$
Anche il numero $\;3^{535}-10$.

Ma probabilmente nessuno dei due numeri è primo.
Puntuale :wink:


Riguardo a b), per dimostrare la divisibilità per 11, osservo che 6¹²³ - 7 = (6³)⁴¹ - 7.
Ora, si trova facilmente che 6³ = 11·19 + 7, vale a dire: 6³ ≡ 7 (mod 11); inoltre: 7¹⁰ ≡ 1 (mod 11), grazie a Fermat, per cui 7⁴¹ ≡ 7 (mod 11).
Tornando a (6³)⁴¹ - 7, ho immediatamente (11·19 + 7)⁴¹ ≡ 7⁴¹ ≡ 7 (mod 11) e dunque 6¹²³ - 7 ≡ 0 (mod 11).

Riguardo ad a), per dimostrare la divisibilità per 7, osservo che 3⁶ = 729 ≡ 1 (mod 7), perciò 3⁵³⁵ ≡ 3 (mod 7), dal momento che 535 = 6·89 +1.
La conclusione cercata, a questo punto, è immediata.
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
(Biagio Marin)

Pasquale
Livello 11
Livello 11
Messaggi: 2563
Iscritto il: mer mag 25, 2005 2:14 am

Re: Può essere?

Messaggio da Pasquale »

Relativamente a 7^345-2 , Decimal Basic non ci credeva ed ha voluto quindi verificare a modo suo, cercando il valore dell'ultima cifra dell'espressione:

LET a=7
FOR m=1 TO 344
LET b=a*7
LET b$=right \$(STR\$(b),1)
LET a=VAL(b\$)
next M
PRINT "ultima cifra ="; a-2
END
_________________

\text {     }ciao Immagine ciao
E' la somma che fa il totale (Totò)

Bruno
Livello 9
Livello 9
Messaggi: 1431
Iscritto il: lun nov 21, 2005 6:07 pm
Località: Bologna

Re: Può essere?

Messaggio da Bruno »

Esatto, Pasquale.

Infatti, per dimostrare la divisibilità per 5 di 7ⁿ - 2, è sufficiente osservare le sue cifre finali, senz'altro cicliche essendo notoriamente cicliche quelle di 7ⁿ. In particolare, per n ≥ 1, abbiamo: 5, 7, 1, 9, 5, 7, 1, 9, ..., e il gioco è fatto :D
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
(Biagio Marin)

Rispondi