TdN for dummies
Se $a$ e $b$ sono coprimi allora
$(a+b, a^2 - ab + b^2) = 1$ oppure $3$
(come al solito $(\cdot, \cdot)$ indica il massimo comun divisore )
$(a+b, a^2 - ab + b^2) = 1$ oppure $3$
(come al solito $(\cdot, \cdot)$ indica il massimo comun divisore )
Risposte
scusami,avrei qualche perplessità:
perchè $b>A$? non era condizione che fosse $b>a_k$ ??
poi mi chiedevo perchè $(k+1)|C+Ak^2$ implica $(k+1)|C+A$
grazie
perchè $b>A$? non era condizione che fosse $b>a_k$ ??
poi mi chiedevo perchè $(k+1)|C+Ak^2$ implica $(k+1)|C+A$
grazie
Guarda fedeb la mia soluzione può essere benissimo errata... ti rispondo cmq...
- si infatti $b>=A$ (ho aggiunto un maggiore-uguale) è una condizione più forte di $b>a_k$, per come è definito A (a parte casi limite). E quindi è sufficiente soddisfare la prima. (NB: sufficiente, non necessario... molti dei passaggi fatti non sono forzati dal problema, è questo che mi fa credere che la mia sol sia errata
);
- per la seconda domanda, supponi che $(k+1)|C+Ak^2$. Vale inoltre (sono identità) anche che:
- $(k+1)|(k+1)^2|A(k+1)^2=Ak^2+2Ak+A$
e quindi k+1 divide sia $C+Ak^2$ che $ak^2+2ak+a^2$ e quindi anche la loro differenza, ovvero $2Ak+A-C$...
Ora di nuovo lo stesso trucco per far andar via anche il $k$. Vale che:
-$(k+1)|2A(k+1)=2Ak+2A$
ed eseguendo la differenza $(k+1)|A+C$...
e inoltre i passaggi sono reversibili, quindi se A+C>0 si trova un $k$ positivo diverso da 0...;
- si infatti $b>=A$ (ho aggiunto un maggiore-uguale) è una condizione più forte di $b>a_k$, per come è definito A (a parte casi limite). E quindi è sufficiente soddisfare la prima. (NB: sufficiente, non necessario... molti dei passaggi fatti non sono forzati dal problema, è questo che mi fa credere che la mia sol sia errata
);- per la seconda domanda, supponi che $(k+1)|C+Ak^2$. Vale inoltre (sono identità) anche che:
- $(k+1)|(k+1)^2|A(k+1)^2=Ak^2+2Ak+A$
e quindi k+1 divide sia $C+Ak^2$ che $ak^2+2ak+a^2$ e quindi anche la loro differenza, ovvero $2Ak+A-C$...
Ora di nuovo lo stesso trucco per far andar via anche il $k$. Vale che:
-$(k+1)|2A(k+1)=2Ak+2A$
ed eseguendo la differenza $(k+1)|A+C$...
e inoltre i passaggi sono reversibili, quindi se A+C>0 si trova un $k$ positivo diverso da 0...;
perfetto, la faccenda della divisibilità è chiarissima, grazie.
pero per quanto riguarda la condizione $b>A$, non mi sembra lecito assumerla come vera e procedere.
il senso è che : non andrebbe dimostrata?? inoltre la dimostrazione funziona sse tale condizione è verificata, no??
grazie
pero per quanto riguarda la condizione $b>A$, non mi sembra lecito assumerla come vera e procedere.
il senso è che : non andrebbe dimostrata?? inoltre la dimostrazione funziona sse tale condizione è verificata, no??
grazie
nel post precedente ho corretto... basta $b>=A$ (anche perchè è quello che riesco ad ottenere alla fine 
)... (supponi di avere già fatto lo step 1 per esempio, da fare a mano)...
e non la ritengo soddisfatta a priori.. poi infatti cerco un $b$ del tipo $b=kA$ e se alla fine troverò un $k$ maggiore od uguale ad 1 (che deve verificare anche le altre proprietà), avrò verificato anche questa condizione, in quanto
$b=kA & k>=1=>b>=A$ (ah la chiarezza delle formule, meglio di mille parole)...
)... (supponi di avere già fatto lo step 1 per esempio, da fare a mano)...e non la ritengo soddisfatta a priori.. poi infatti cerco un $b$ del tipo $b=kA$ e se alla fine troverò un $k$ maggiore od uguale ad 1 (che deve verificare anche le altre proprietà), avrò verificato anche questa condizione, in quanto
$b=kA & k>=1=>b>=A$ (ah la chiarezza delle formule, meglio di mille parole)...
"Levacci":
Vediamo come viene...
Si deve avere $3*(sum_(i=0)^n 10^i*a_i)=2*(sum_(i=1)^n 10^i*a_(i-1)+a_n)$. Quindi risulta $(3*10^n-2)*a_n=2*(sum_(i=1)^n 10^i*a_(i-1)) - 3*(sum_(i=0)^n 10^i*a_i).$ Con qualche manipolazione RHS diventa $17*(sum_(i=0)^(n-1) 10^i*a_i)$ o equivalentemente $17*(a_(n-1) a_(n-2) ... a_1 a_0)$, quest'ultima notazione indica il numero di $n$ cifre $a_i$. Sappiamo che $a_n$ è $<=9$ quindi $17$ deve dividere $(3*10^n-2)$. Cerco il minimo $n$ per il quale risulti $3*10^n=2 (mod 17)$. Sapendo che l'inverso di $3 (mod17)$ è $6$, si deve risolvere $10^n=12 (mod 17)$. Un po' di simpatici conti e si trova $n=15$. Per trovare il minimo poniamo $a_n=1$ e troviamo le restanti cifre con $(3*10^15-2)/17$, l'idra a sedici teste che ho scritto poco sopra.
Se ho esagerato con la sintesi o con la distrazione, fatemi sapere. I problemi proposti da tom, come al solito, sono ottimi.
riguardo al problema precedente, potreste spiegarmi questo passaggio?
Sapendo che l'inverso di $3 (mod17)$ è $6$, si deve risolvere $10^n=12 (mod 17)$. Un po' di simpatici conti e si trova $n=15$
per il resto ce l'ho fatta da solo,
ma quando dovevo trovare il numero divisibile per diciassette l'ho fatto per tentativi...grazie, ciao a tutti
Riconosco che l'aggettivo "simpatici" è fuorviante per due ragioni: si parla di contabilità e inoltre i conti sono un gran numero. Risolvendo il problema, sono riuscito a saltare qualche tentativo per merito di un paio di considerazioni euristiche. Dunque, si tratta di trovare un $n$ per il risulti $10^n=12 (mod 17)$. Mi sono accorto che $12$, guarda caso, è l'inverso di $10$, a questo aggiungi che $10^15 * 10 = 1 (mod 17)$ (grazie a Fermat e al suo piccolo teorema) e il gioco è fatto. Tutto questo, contando poco .
.
postate qualcos'altro... mi stavo divertendo un sacco 
volentieri
dimostrare che 41 non puo essere scritto come differenza di potenze di due e tre
in termini decenti, non esistono $n,m,j,k$ naturali tali che
$41=2^n-3^m$ e $41=3^j-2^k$
dimostrare che 41 non puo essere scritto come differenza di potenze di due e tre
in termini decenti, non esistono $n,m,j,k$ naturali tali che
$41=2^n-3^m$ e $41=3^j-2^k$
Per il primo, lavoriamo modulo $8$. $41=1$ e $2^n=0$ per $n>2$. Dobbiamo quindi dimostrare che non esiste un $m$ per cui valga $-3^m=1 (mod 8)$. Per $m$ pari abbiamo $-3^(2a)=-(3^2)^a=-1 (mod 8)$. In modo analogo si fa vedere che per $m$ dispari il residuo è $-3$. Restano solo da verificare i casi i cui $n=0,1$ e questi si fanno allegramente via manu propria.
Presto anche il secondo problema, sempre su queste reti .
Presto anche il secondo problema, sempre su queste reti
.
Dato che Levacci si fa attendere (anche se credo che il secondo caso sia analogo al primo..) posto un problemino piuttosto semplice per ingannare l'attesa
Trovare il Massimo Comun Divisore di tutti i numeri della forma $n^73-n$, con $n inNN$. Buon divertimento!
Trovare il Massimo Comun Divisore di tutti i numeri della forma $n^73-n$, con $n inNN$. Buon divertimento!
L'ultimo problema della serie è rimasto irrisolto - che peccato. Gli rispondo, così, proponendone una generalizzazione.
Dato un primo $p \in ZZ$, determinare il massimo comun divisore dell'insieme $\{n^p - n\}_{n \in \mathbb{Z}}$.
Dato un primo $p \in ZZ$, determinare il massimo comun divisore dell'insieme $\{n^p - n\}_{n \in \mathbb{Z}}$.
Mi pare evidente che (a-2)! sia congruo a 0 (mod a) per ogni a composto.
Infatti ogni fattore di a è necessariamente <= a/2 e quindi <= (a-2). Ne segue che è contenuto in (a-2)!
O sbaglio?
Infatti ogni fattore di a è necessariamente <= a/2 e quindi <= (a-2). Ne segue che è contenuto in (a-2)!
O sbaglio?
"Iacopo":... eppure $4$ non divide $2!$. Quindi il tuo ragionamento, da qualche parte, deve pur fallire. Inoltre non è chiaro - almeno a me - a quale problema tu stia rispondendo.
Mi pare evidente che (a-2)! sia congruo a 0 (mod a) per ogni a composto.
Infatti ogni fattore di a è necessariamente <= a/2 e quindi <= (a-2). Ne segue che è contenuto in (a-2)!
O sbaglio?
Infatti ho scritto una cavolata, rispondendo a un problema posto un po' di tempo fate. Scusate.
"Gabriel":
L'ultimo problema della serie è rimasto irrisolto - che peccato. Gli rispondo, così, proponendone una generalizzazione.
Dato un primo $p \in ZZ$, determinare il massimo comun divisore dell'insieme $\{n^p - n\}_{n \in \mathbb{Z}}$.
Vorrei rispondere con la limitazione $ninNN$, la generalizzazione a $ZZ$ ci penso domani.. Per i casi $n=0,1$ si vede bene che esistono infiniti divisori del nostro $t=n^p-n$. Osserviamo che, se $n$ è pari, $t$ è pari, mentre se $n$ è dispari, $t$ è comunque pari. Quindi $2$ è un divisore.
Vediamo poi che $p$ è un divisore, in quanto per il piccolo teorema di Fermat $n^p=n(modp)$.
Fuori da questi casi particolari, si ha che $AAq$ primo $n^p-n=0(modq)<=>n^(p-1)=1(modq)$, perchè il caso $n=0(mod q)$ è stato escluso, visto che non crea problemi. Sappiamo che per $q$ primo $n^(q-1)=1(mod q)$ (sempre a condizione che $(n,q)=1$)e quindi vale anche $n^(k*(q-1))=(n^(q-1))^k=1(mod q)$.
Quindi se $EE kinZZ$ tale che $(q-1)*k=p-1$, cioè se $q-1|p-1$ abbiamo che $n^(p-1)=1(modq)$, cioè $q$ è un divisore di $t$. Detto $q(i)$ l'i-esimo primo ($q(1)=2$ $q(2)=3$ ...) definiamo $A={q(i) | i in NN, q(i)-1|p-1}$. Allora l'MCD dell'insieme ${n^p - n}$ è il prodotto di tutti gli elementi di $A$.
Che ne dite, è giusta? Quando ho postato il caso con $p=73$ non ero del tutto sicuro della soluzione, ho postato anche per avere conferme o smentite. Alla fine poi mi sono risposto da solo. Spero qualcosa di buono ci sia in quello che ho scritto..
caio
"alvinlee88":
Vorrei rispondere con la limitazione $ninNN$, la generalizzazione a $ZZ$ ci penso domani.. Per i casi $n=0,1$ si vede bene che esistono infiniti divisori del nostro $t=n^p-n$. Osserviamo che, se $n$ è pari, $t$ è pari, mentre se $n$ è dispari, $t$ è comunque pari. Quindi $2$ è un divisore.
Vediamo poi che $p$ è un divisore, in quanto per il piccolo teorema di Fermat $n^p=n(modp)$.
Fuori da questi casi particolari, si ha che $AAq$ primo $n^p-n=0(modq)<=>n^(p-1)=1(modq)$, perchè il caso $n=0(mod q)$ è stato escluso, visto che non crea problemi. Sappiamo che per $q$ primo $n^(q-1)=1(mod q)$ (sempre a condizione che $(n,q)=1$)e quindi vale anche $n^(k*(q-1))=(n^(q-1))^k=1(mod q)$.
Quindi se $EE kinZZ$ tale che $(q-1)*k=p-1$, cioè se $q-1|p-1$ abbiamo che $n^(p-1)=1(modq)$, cioè $q$ è un divisore di $t$. Detto $q(i)$ l'i-esimo primo ($q(1)=2$ $q(2)=3$ ...) definiamo $A={q(i) | i in NN, q(i)-1|p-1}$. Allora l'MCD dell'insieme ${n^p - n}$ è il prodotto di tutti gli elementi di $A$. [...] Spero qualcosa di buono ci sia in quello che ho scritto.
Di buono c'è tanto, ma andrebbe un attimino risistemato ... In sintesi, tu affermi che, qualunque sia $p \in NN$, purché primo, il massimo comun divisore $m_p$ dell'insieme $\{n^p-n\}_{n \in ZZ}$ è divisibile per $p$ e per qualunque altro primo $q \in NN$ tale che $(q-1) | (p-1)$. Questo, tuttavia, non dice nulla di definitivo sulla fattorizzazione di $m_p$, visto che - in linea di principio - non stabilisce quale sia il massimo esponente $\alpha \in NN$ con cui un generico primo $q \in NN$ possa dividere $m_p$ né esclude la possibilità che esistano divisori primi di $m_p$, diversi da quelli già elencati. In ogni caso, è di per sé già un buon inizio.
Giustissimo, sono andato di fretta. Vedo di rimediare. Dimostro che non ne esistono altri oltre a quelli che ho detto io (dopo dimostrerò che gli esponenti dei $qinA$ devono essere per forza $1$), cioè voglio dimostrare che, per $q$ primo, $q|n^p-n =>qinA$, ovverosia "$q$ non appartiene ad $A$"$ =>$"$q$ non divide $n^p-n$".
Se $q$ non appartiene a $A$, allora, per definizione di $A$, $q-1$ non divide $p-1$, cioè $p-1=(q-1)k+h$, con $k,h in ZZ$, con $h!=0(mod q-1)$ (perchè altrimenti avremmo che $(q-1)|p-1$). Poichè $n^p-n\equiv0(modq)<=>n^(p-1)\equiv1(modq)$ (sempre con le condizioni dell'altro post), dimostriamo che $n^(p-1)!=1(modq)$, con l'ipotesi $p-1=(q-1)k+h$, con $k,h in ZZ$, con $h!=0(mod q-1)$. Se per assurdo fosse $n^(p-1)\equiv1(modq)$, si avrebbe $n^(k*(q-1))*n^h\equiv1(modq)$, cioè $n^h\equiv1(modq)$ , in quanto $n^(k*(q-1))\equiv1(modq))$ (poichè $n^(q-1)\equiv1(modq)$ per Fermat, con la solita condizione su n e q), ma $n^h\equiv1(modq)$ se e solo se $h$ è un multiplo dell'ordine di $n$ in $q$, che è $q-1$. Ma $h!=0(mod q-1)$ per ipotesi. Assurdo. Quindi i possibili divisori sono tutti e soli gli elementi di $A$, e dunque il massimo primo che divide $n^p-n$ è proprio $p$. Dimostriamo ora che non possono esserci esponenti maggiori di $1$ per gli elementi di $A$
$m_p$ deve per definizione dividere ogni elemento del'insieme $B={n^p-n}_(n inNN)$, quindi in particolare deve dividere $q^p-q=q(q^(p-1)-1)$, con $q in A$ . Sia$a inNN$. Si vede che per ogni $a>1$, $q^a$ non divide $q^p-q$, perchè se $a<=p$ allora $q^(a-1)$ deve dividere $q^(p-1) -1$, e questo è impossibile poichè $q^(a-1)|q^(p-1)$, mentre se $a>=p+1$ dovrebbe essere che $q^(p+j)$, con $j>=0$, divide $q^(p-1)-1$ chiaramente impossibile. Quindi nessun esponente dei $qinA$ può essere maggiore di $1$.
In conclusione, $m_p$ è proprio il prodotto di tutti gli elementi di $A$.
Che ne pensi?
Se $q$ non appartiene a $A$, allora, per definizione di $A$, $q-1$ non divide $p-1$, cioè $p-1=(q-1)k+h$, con $k,h in ZZ$, con $h!=0(mod q-1)$ (perchè altrimenti avremmo che $(q-1)|p-1$). Poichè $n^p-n\equiv0(modq)<=>n^(p-1)\equiv1(modq)$ (sempre con le condizioni dell'altro post), dimostriamo che $n^(p-1)!=1(modq)$, con l'ipotesi $p-1=(q-1)k+h$, con $k,h in ZZ$, con $h!=0(mod q-1)$. Se per assurdo fosse $n^(p-1)\equiv1(modq)$, si avrebbe $n^(k*(q-1))*n^h\equiv1(modq)$, cioè $n^h\equiv1(modq)$ , in quanto $n^(k*(q-1))\equiv1(modq))$ (poichè $n^(q-1)\equiv1(modq)$ per Fermat, con la solita condizione su n e q), ma $n^h\equiv1(modq)$ se e solo se $h$ è un multiplo dell'ordine di $n$ in $q$, che è $q-1$. Ma $h!=0(mod q-1)$ per ipotesi. Assurdo. Quindi i possibili divisori sono tutti e soli gli elementi di $A$, e dunque il massimo primo che divide $n^p-n$ è proprio $p$. Dimostriamo ora che non possono esserci esponenti maggiori di $1$ per gli elementi di $A$
$m_p$ deve per definizione dividere ogni elemento del'insieme $B={n^p-n}_(n inNN)$, quindi in particolare deve dividere $q^p-q=q(q^(p-1)-1)$, con $q in A$ . Sia$a inNN$. Si vede che per ogni $a>1$, $q^a$ non divide $q^p-q$, perchè se $a<=p$ allora $q^(a-1)$ deve dividere $q^(p-1) -1$, e questo è impossibile poichè $q^(a-1)|q^(p-1)$, mentre se $a>=p+1$ dovrebbe essere che $q^(p+j)$, con $j>=0$, divide $q^(p-1)-1$ chiaramente impossibile. Quindi nessun esponente dei $qinA$ può essere maggiore di $1$.
In conclusione, $m_p$ è proprio il prodotto di tutti gli elementi di $A$.
Che ne pensi?
"alvinlee88":
[...] ma $n^h\equiv1(modq)$ se e solo se $h$ è un multiplo dell'ordine di $n$ in $q$, che è $q-1$. [...]
Tutto a posto, con la sola eccezione della proposizione quotata qui sopra, dal momento che l'ordine moltiplicativo di $q$ alla base $n$ non è necessariamente $q-1$, bensì - in generale - un suo divisore. A meno che $n$ non sia una radice primitiva modulo $q$.
"Gabriel":
Dato un primo $p \in ZZ$, determinare il massimo comun divisore dell'insieme $\{n^p - n\}_{n \in \mathbb{Z}}$.
"fedeb":
non esistono $n,m,j,k$ naturali tali che $41=3^j-2^k$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo