Trovare $n$ da $n^14$?
"Il numero $114197726928752863294965276721$ è la quattoridicesima potenza di un intero positivo $n$. Determinare tale $n$".
Buonasera a tutti.
Inizio ad odiare questo tipo di problemi, tempo fa ne avevo proposto uno simile chiedendo spiegazioni e mi sembrava di aver capito; ora mi rendo conto di non avere ancora le idee del tutto chiare.
Ecco i miei (miseri) ragionamenti. $n^14$ è dispari $=>n$ è dispari. $n^14$ è formato da $30$ cifre, dunque è $n^14<10^30$, ma questo mi è poco utile, perchè mi dice solo che $n<10^(15/7)$. Non mi sembra di poter applicare Fermat (il Piccolo) perchè $15= (14+1)$ non è primo; idem dicasi per Eulero. Che fare?
Signori, vi chiedo scusa ma non sono capace. Imploro il vostro aiuto. Perdonate la mia ignoranza; grazie in anticipo.
In attesa di delucidazioni, un cordiale saluto.
Paolo
P.S. Dimenticavo di dire che il tutto deve essere fatto (ovviamente) senza l'uso di calcolatrice (precisazione che può sembrare superflua, ma non lo è, vero Sergio?
)
Ciao, Paolo.
Buonasera a tutti.
Inizio ad odiare questo tipo di problemi, tempo fa ne avevo proposto uno simile chiedendo spiegazioni e mi sembrava di aver capito; ora mi rendo conto di non avere ancora le idee del tutto chiare.
Ecco i miei (miseri) ragionamenti. $n^14$ è dispari $=>n$ è dispari. $n^14$ è formato da $30$ cifre, dunque è $n^14<10^30$, ma questo mi è poco utile, perchè mi dice solo che $n<10^(15/7)$. Non mi sembra di poter applicare Fermat (il Piccolo) perchè $15= (14+1)$ non è primo; idem dicasi per Eulero. Che fare?
Signori, vi chiedo scusa ma non sono capace. Imploro il vostro aiuto. Perdonate la mia ignoranza; grazie in anticipo.
In attesa di delucidazioni, un cordiale saluto.
Paolo
P.S. Dimenticavo di dire che il tutto deve essere fatto (ovviamente) senza l'uso di calcolatrice (precisazione che può sembrare superflua, ma non lo è, vero Sergio?
) Ciao, Paolo.
Risposte
Stabiliamo quanto può essere grosso quest'intero. Come hai scritto tu stesso, vale anzitutto $1\le n < 10^{15/7}$, da cui (per le proprietà di monotonia del logaritmo): $\log_{10}(n) < 15/7$. Quindi $1 + \lfloor \log_{10}(n)\rfloor \le 1 + \lfloor 15/7 \rfloor = 3$. Sennonché, detto $k$ il numero delle cifre decimali (significative) di $n$, è precisamente $k = 1 + \lfloor \log_{10}(n)\rfloor $, da cui $k\le 3$. D'altronde, è chiaro che $k > 2$, dal momento che $100^{14} < 10^{29} < a$, dove $a$ è il numeraccio del problema. Dunque, necessariamente, $k = 3$ e $10^2 < n < 10^3$. Adesso riesci a concludere da solo?
EDIT: l'italiano è importante.
EDIT: l'italiano è importante.
"Gabriel":
Anzitutto stabiliamo quanto può essere grosso quest'intero. Come hai scritto tu stesso, vale anzitutto $1\le n < 10^{15/7}$, da cui (per le proprietà di monotonia del logaritmo): $\log_{10}(n) < 15/7$. Quindi $1 + \lfloor \log_{10}(n)\rfloor \le 1 + \lfloor 15/7 \rfloor = 3$. Sennonché, detto $k$ il numero delle cifre decimali (significative) di $n$, è precisamente $k = 1 + \lfloor \log_{10}(n)\rfloor $, da cui $k\le 3$. D'altronde, è chiaro che $k > 2$, dal momento che $100^{14} < 10^{29} < a$, dove $a$ è il numeraccio del problema. Dunque, necessariamente, $k = 3$ e $10^2 < n < 10^3$. Adesso riesci a concludere da solo?
Ciao Gabriel, anzitutto grazie per la tua risposta.
Confesso che ho seguito con difficoltà i tuoi ragionamenti, non perchè non fossero chiari (anzi, complimenti per la spiegazione) ma perchè non ci sono abituato e speravo esistesse un metodo più veloce. Comunque, al di là di ciò, ora sappiamo che $n$ ha tre cifre (quindi è compreso tra $100$ e $999$). Che altro sappiamo? Devo giocare un po' con le congruenze? Questa strada però non mi pare utile, visto che - come dicevo già prima - nè Fermat nè Eulero sono applicabili. Gentilmente puoi darmi ancora un hint?
Grazie mille davvero per il tuo aiuto.
Paolo
Una buona idea sarebbe di abbassare l'upper bound per $n$. Ad es., è evidente che $n < 200$, perché $200^{14} = 2^{14} * 10^{28} > 10^{30}$, visto che $2^{14} > 100$. Anzi c'è un significativo margine che consente di ridurlo ulteriormente - provaci!
Ad esempio, posso fare questo: prendiamo $130=2*5*13$. Voglio confrontare $130^14$ e $10^30$. Non sapendo quale dei due è maggiore, suppongo che sia
$130^14<10^30$
Prendendo i logaritmi decimali
$14*log130<30$
$log130<30/14$
Quindi
$\lfloor log130 \rfloor <\lfloor 30/14 \rfloor $
$\lfloor log130 \rfloor <2 $
Ora sicuramente quest'ultima diseguaglianza è errata, visto che $log130$ sarà senz'altro maggiore di $2 = log100$.
Quindi, sappiamo che $100
Grazie ancora per l'aiuto.
$130^14<10^30$
Prendendo i logaritmi decimali
$14*log130<30$
$log130<30/14$
Quindi
$\lfloor log130 \rfloor <\lfloor 30/14 \rfloor $
$\lfloor log130 \rfloor <2 $
Ora sicuramente quest'ultima diseguaglianza è errata, visto che $log130$ sarà senz'altro maggiore di $2 = log100$.
Quindi, sappiamo che $100
Grazie ancora per l'aiuto.
Non capisco il senso dello scandalo. Se fosse possibile utilizzare soltanto delle disuguaglianze, per decidere la soluzione del problema, che male ci sarebbe mai, perdonami?! Ad ogni modo, trovo difficile poter stringere a mano più di quanto già tu non abbia fatto, per cui adesso serve pensare a qualcos'altro. Per es., sai dirmi quando un numero (in base decimale) è divisibile per 3? E per 5? E per 7? E, in generale, per un qualche primo naturale $p$ tale che $\gcd(10,p) = 1$?
"Gabriel":
Non capisco il senso dello scandalo. Se fosse possibile utilizzare soltanto delle disuguaglianze, per decidere la soluzione del problema, che male ci sarebbe mai, perdonami?!
No, no figurati. Nessuno scandalo, tranquillo. E' solo che non ero abituato a ragionare in questo modo e allora mi sembrava strano, tutto qui. Grazie comunque per avermi insegnato che anche le diseguaglianze aiutano.
"Gabriel":
Ad ogni modo, trovo difficile poter stringere a mano più di quanto già tu non abbia fatto, per cui adesso serve pensare a qualcos'altro. Per es., sai dirmi quando un numero (in base decimale) è divisibile per 3? E per 5? E per 7? E, in generale, per un qualche primo naturale $p$ tale che $\gcd(10,p) = 1$?
1. Un numero è divisibile per 3 quando la somma delle sue cifre è divisibile per 3.
2. Un numero è divisibile per 5 se termina con 0 o con 5.
3. Un numero è divisibile per 7 se... AIUTO! non lo so! Qual è il criterio di divisibilità per 7?
Grazie ancora, carissimo, per il tuo prezioso aiuto.
Si prende la cifra più a sinistra del numero, la si moltiplica per 3, e si somma alla cifra immediatamente a destra. Questa quantità ottenuta, portandola a modulo 7, di nuovo si moltiplica per 3 e si somma alla cifra immediatamente a destra, e così via.. Se la cifra finale è 0 (sempre a modulo 7),il numero è divisibile per 7.
Sì, elios ha suggerito un criterio - elementare conseguenza del fatto che $10 = 3$ mod 7. Più in generale, supponi sia $b\ge 2$ un intero e che $(a_m,\ldots,a_1,a_0)_b$ sia una rappresentazione posizionale in base $b$ di un certo $n \in NN = \{1, 2,\ldots\}$, dove $a_k \in \{0, 1, \ldots, b-1\}$, per ogni $k = 0, 1, \ldots, m$. Se $p \in NN_0$ è primo e $\gcd(b,p) = 1$, l'insieme $K_p = \{k \in NN: b^k \equiv 1 \mbox{mod} p\}$ è non vuoto, quindi possiede un elemento minimo. Sia, pertanto, $\omega = \min(K_p)$. Per ogni $k = 0, 1, \ldots, \omega-1$, diciamo $r_k$ il resto minimo assoluto di $b^k$ mod p, cioè il più piccolo intero congruo a $b^k$ modulo p il cui valore assoluto è $\le \lfloor $(p-1)/2$\rfloor$. Allora:
TEOREMA: $n$ è divisibile per $p$ se e soltanto se $\sum_{k=0}^{r-1} \sum_{i=0}^{\omega - 1} a_{k\omega + i}r_i $, pur di ammettere [come sempre è lecito, salvo diversamente aggiungere degli zeri in testa all'(m+1)-upla $(a_m,\ldots,a_1,a_0)$] che $m+1$ sia un multiplo di $\omega$ e assumere di conseguenza $r = (m+1)$/$\omega$.
Torniamo, quindi, al problema. Con le notazioni dei post precedenti, $a$ non è, chiaramente, divisibile per $5$. Che sia divisibile per 7? Proviamo ad applicare il teorema qui sopra. Modulo 7, vale $r_0 = 1$, $r_1 = 10^1 = 3$, $r_2 = 10^2 = 2$, $r_3 = 10^3 = -1$, $r_4 = 10^4 = -3$ ed $r_5 = 10^5 = -2$, per cui $\omega = 6$. D'altronde, $m+1 = 30$, e quindi $r = 5$. Si tratta, di conseguenza, di ridurre modulo 7 la somma $s :=\sum_{k=0}^4 (a_{6k} + 3a_{6k+1} + 2a_{6k+2} - a_{6k+3} - 3a_{6k+4} -2a_{6k+5})$. Conti alla mano, si trova $s \equiv 0$ mod 7. Perciò 7 divide $a$. Siccome $100 < a < 130$, ne segue che i candidati possibili sono 105, 112, 119 e 126. Di questi, il primo è da scartare perché divisibile per 5; il secondo e il quarto perché pari. La soluzione cercata, di conseguenza, è proprio 119.
TEOREMA: $n$ è divisibile per $p$ se e soltanto se $\sum_{k=0}^{r-1} \sum_{i=0}^{\omega - 1} a_{k\omega + i}r_i $, pur di ammettere [come sempre è lecito, salvo diversamente aggiungere degli zeri in testa all'(m+1)-upla $(a_m,\ldots,a_1,a_0)$] che $m+1$ sia un multiplo di $\omega$ e assumere di conseguenza $r = (m+1)$/$\omega$.
Torniamo, quindi, al problema. Con le notazioni dei post precedenti, $a$ non è, chiaramente, divisibile per $5$. Che sia divisibile per 7? Proviamo ad applicare il teorema qui sopra. Modulo 7, vale $r_0 = 1$, $r_1 = 10^1 = 3$, $r_2 = 10^2 = 2$, $r_3 = 10^3 = -1$, $r_4 = 10^4 = -3$ ed $r_5 = 10^5 = -2$, per cui $\omega = 6$. D'altronde, $m+1 = 30$, e quindi $r = 5$. Si tratta, di conseguenza, di ridurre modulo 7 la somma $s :=\sum_{k=0}^4 (a_{6k} + 3a_{6k+1} + 2a_{6k+2} - a_{6k+3} - 3a_{6k+4} -2a_{6k+5})$. Conti alla mano, si trova $s \equiv 0$ mod 7. Perciò 7 divide $a$. Siccome $100 < a < 130$, ne segue che i candidati possibili sono 105, 112, 119 e 126. Di questi, il primo è da scartare perché divisibile per 5; il secondo e il quarto perché pari. La soluzione cercata, di conseguenza, è proprio 119.
Eccomi qui, scusate il ritardo con cui rispondo ma sono stato molto impegnato in questi ultimi giorni.
Dunque, anzitutto grazie elios per aver citato un buon criterio di divisibilità per 7 che personalmente non conoscevo.
Quanto a Gabriel, grazie molte anche a te; il problema ora è risolto, anche se confesso che ho avuto un paio di difficoltà a capire il teorema che hai enunciato; tuttavia, ora, con l'esempio di applicazione che hai dato nella risoluzione del problema è tutto più chiaro.
Grazie mille. Ora mi inventerò altri problemi del genere e vi farò sapere se ci sono ancora dubbi. Grazie.
Dunque, anzitutto grazie elios per aver citato un buon criterio di divisibilità per 7 che personalmente non conoscevo.
Quanto a Gabriel, grazie molte anche a te; il problema ora è risolto, anche se confesso che ho avuto un paio di difficoltà a capire il teorema che hai enunciato; tuttavia, ora, con l'esempio di applicazione che hai dato nella risoluzione del problema è tutto più chiaro.
Grazie mille. Ora mi inventerò altri problemi del genere e vi farò sapere se ci sono ancora dubbi. Grazie.
Prego.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo