Grandi numeri e piccoli divisori

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
franco
Livello 8
Livello 8
Messaggi: 1285
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Grandi numeri e piccoli divisori

Messaggio da franco »

1. Dimostrare che $10^n + 1$ è divisibile per $13$ quando $n = 3^{301}$
2. Dimostrare che $10^n + 1$ è divisibile per $257$ quando $n =127616$

www.diophante.fr
A393

Q1 Démontrer que 10^n + 1 est divisible par 13 quand n = 3^301
Q2 Démontrer que 10^n + 1 est divisible par 257 quand n =127616
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

Quelo
Livello 6
Livello 6
Messaggi: 569
Iscritto il: ven giu 16, 2006 3:34 pm

Re: Grandi numeri e piccoli divisori

Messaggio da Quelo »

franco ha scritto:
sab ott 09, 2021 11:01 am
1. Dimostrare che $10^n + 1$ è divisibile per $13$ quando $n = 3^{301}$
Un numero è divisibile per 13 se, diviso in terzetti da destra, la differenza tra la somma dei resti mod 13 dei terzetti in posizione dispari e la somma dei resti mod 13 dei terzetti in posizione pari è pari a 0 o multiplo di 13
Per esempio $10^3+1=1|001$ è divisibile per 13 perché sia il primo che il secondo terzetto danno resto 1, la differenza è quindi zero.
Se inseriamo 6 zeri la situazione non cambia:
$10^9+1=1|000|000|001 \equiv 0 \pmod{13} = 0$
Quindi $10^{3k}+1 \equiv 0 \pmod{13}$ con $k$ dispari
se poniamo $k=3^{300}$ che è sicuramente dispari essendo potenza di 3, otteniamo
$10^{3^{301}}+1 \equiv 0 \pmod{13}$
e più in generale
$10^{3^k}+1 \equiv 0 \pmod{13}$ per $k>0$
[Sergio]

Quelo
Livello 6
Livello 6
Messaggi: 569
Iscritto il: ven giu 16, 2006 3:34 pm

Re: Grandi numeri e piccoli divisori

Messaggio da Quelo »

franco ha scritto:
sab ott 09, 2021 11:01 am
2. Dimostrare che $10^n + 1$ è divisibile per $257$ quando $n =127616$
L'inverso di un numero primo $p>5$ è un numero periodico con periodo di $p-1$ cifre o frazione intera di $p-1$ (non chiedetemi il perché, io l'ho ricavato sperimentalmente)
Ad esempio 1/7 ha periodo di 6 cifre, 1/11 ha periodo di 2 cifre (10/5), 1/13 ha periodo di 6 cifre (12/2), 1/17 ha periodo di 16 cifre e così via
Di conseguenza può essere scritto come rapporto tra un numero intero $x$ e $10^{p-1}-1$

$\displaystyle \frac{1}{257}$ ha periodo di 256 cifre, quindi scriviamo $\displaystyle \frac{1}{257}=\frac{x}{10^{256}-1}$

$\displaystyle 10^n+1 \equiv 0 \pmod{257}$ significa che $\displaystyle \frac{(10^n+1)x}{10^{256}-1}$ è un numero intero

Scriviamo $\displaystyle \frac{(10^n+1)x}{(10^{128}+1)(10^{128}-1)}$ e poniamo $n=128$

Con ausilio informatico scopriamo che $\displaystyle \frac{x}{10^{128}-1}$ è un numero intero
Quindi $n=128$ è una soluzione e di conseguenza lo sono tutte quelle nella forma $n=256m+128$ in quanto $10^{(2k+1)n}+1$ è multiplo di $10^n+1$

$127616=256\cdot498+128$
[Sergio]

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

Re: Grandi numeri e piccoli divisori

Messaggio da Bruno »

Bravo, Sergio :D
(Bruno)

...........................
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
{Biagio Marin}
................................................................
Meglio soluzioni sbagliate che risposte esatte.
{Rudi Mathematici}

Rispondi