MCD
Ciao a tutti!
Frequento l'uni a Crema di Sicurezza Informatica e ho l'esame di matematica del discreto a breve.
Ho un dubbio su un esercizio che recita:
Come si risolve sto esercizio?
grazie!
Frequento l'uni a Crema di Sicurezza Informatica e ho l'esame di matematica del discreto a breve.
Ho un dubbio su un esercizio che recita:
Dati due numeri interi x e y, con MCD(x,y)=6, quali sono i possibili valori per MCD(x^3,y^4)?
Come si risolve sto esercizio?
grazie!
Risposte
[mod="dissonance"]Benvenuto nel forum! Sposto questo topic nella sezione più appropriata (Algebra). [/mod] Inoltre ti consiglio di scrivere esplicitamente il tuo tentativo di risoluzione specificando i tuoi dubbi, così da facilitare la vita a chi ti voglia rispondere (come tra l'altro è previsto dal regolamento - clic - punto 1.4). Grazie.
Grazie e scusami!
I miei dubbi sono che non capisco come si possa risolvere quell'esercizio avendo 2 incognite e 1 dato!
I miei dubbi sono che non capisco come si possa risolvere quell'esercizio avendo 2 incognite e 1 dato!
Parti dalla definizione di $MCD$...
Si quella la so 
Ma come ci arrivo a trovare x e y?
Ma come ci arrivo a trovare x e y?
Non devi mica trovare [tex]x[/tex] e [tex]y[/tex]: devi trovare [tex]\gcd(x^{3},y^{4})[/tex].
Se [tex]\gcd(x,y)=6[/tex] allora [tex]6[/tex] come si comporta rispetto a [tex]x[/tex] e [tex]y[/tex]? Li divide o non li divide? Se li divide, cosa comporta questo in una eventuale scomposizione di [tex]x[/tex] e di [tex]y[/tex]? E se poi scompongo [tex]x^{3}[/tex] e [tex]y^{4}[/tex], che cosa trovo in queste scomposizioni?
Se [tex]\gcd(x,y)=6[/tex] allora [tex]6[/tex] come si comporta rispetto a [tex]x[/tex] e [tex]y[/tex]? Li divide o non li divide? Se li divide, cosa comporta questo in una eventuale scomposizione di [tex]x[/tex] e di [tex]y[/tex]? E se poi scompongo [tex]x^{3}[/tex] e [tex]y^{4}[/tex], che cosa trovo in queste scomposizioni?
Essendo l'MCD 6 divide $x$ e $y$.
E questo non riesco a capirlo: come li scompongo $x$ e $y$? E $x^3$ e $y^4$?
Sono delle incognite come faccio a scomporle??
E questo non riesco a capirlo: come li scompongo $x$ e $y$? E $x^3$ e $y^4$?
Sono delle incognite come faccio a scomporle??
$x=6*\alpha$,
$y=6*\beta$
perchè
$6$ divide sia $x$ che $y$. Ma, poichè è il MCD di $x$ ed $y$, vuol
dire che il MCD di $\alpha$ e $\beta$ è 1 ($\alpha$ e $\beta$ non hanno fattori in comune).
Per esempio:
$x=6*13^2*2^5$
$y=6*11^2*3^5$.
$y=6*\beta$
perchè
$6$ divide sia $x$ che $y$. Ma, poichè è il MCD di $x$ ed $y$, vuol
dire che il MCD di $\alpha$ e $\beta$ è 1 ($\alpha$ e $\beta$ non hanno fattori in comune).
Per esempio:
$x=6*13^2*2^5$
$y=6*11^2*3^5$.
Ahhhhh capito!!!!
Finalmente!
Molto gentile
Finalmente!
Molto gentile
Sia $zinZ$ e sia $MCD(z,37)=1$ . Stabilire quanto vale $z^73 mod37$
E questo??? È sotto il capitolo "Congruenze e sistemi di congruenze"....ma non capisco come risolverlo coi metodi delle congruenze -.-''
Io penso che $z=73$ perchè se $MCD(a,b)=1$ --> $a^a mod b \equiv 1$
È giusto come ragionamento?
Controesempio: $MCD(4,5)$ --> $4^4 mod 5 \equiv 1$
E questo??? È sotto il capitolo "Congruenze e sistemi di congruenze"....ma non capisco come risolverlo coi metodi delle congruenze -.-''
Io penso che $z=73$ perchè se $MCD(a,b)=1$ --> $a^a mod b \equiv 1$
È giusto come ragionamento?
Controesempio: $MCD(4,5)$ --> $4^4 mod 5 \equiv 1$
"pol20":
Io penso che $z=73$
ma non puoi determinare un valore di $z$, è un qualunque numero intero coprimo con $37$, la domanda è trovare:
[tex]$z^{73} \bmod{37}$[/tex], non è possibile determinare $z$ !
"pol20":
$MCD(a,b)=1$ --> $a^a mod b \equiv 1$
questo è proprio tanto falso, non è che ti confondi con altro?
"pol20":
È giusto come ragionamento?
anche come ragionamento è sbagliato. Se anche fosse vero il teorema che dici, comunque non varrebbe la tua implicazione, perchè il "teorema" che ti sei inventato dice un'altra cosa!
"pol20":
Controesempio: $MCD(4,5)$ --> $4^4 mod 5 \equiv 1$
controesempio a cosa? hai usato il termine un po' a caso, e comunque non dimostra niente.
Questo esercizio si risolve con il piccolo teorema di Fermat, l'hai fatto?
XD un casino dietro l'altro...
Si, l'ho fatto, la formula è questa:
$a^p \equiv a (mod p)$
Quindi diverrebbe:
$z^37 \equiv z(mod37)$
Si, l'ho fatto, la formula è questa:
$a^p \equiv a (mod p)$
Quindi diverrebbe:
$z^37 \equiv z(mod37)$
Se $p$ e' un numero primo e $a$ non e' un multiplo di $p$ allora $a^(p-1)-=1_(mod_p)$
$z^(73-1)-=1_mod_73$
prova un po'....
Edit: ho letto male il modulo.... non e' 73, ma 37....adesso mi viene il dubbio
$z^(73-1)-=1_mod_73$
prova un po'....
Edit: ho letto male il modulo.... non e' 73, ma 37....adesso mi viene il dubbio
Non riesco ad andare fuori...
Ho mandato una mail alla prof ma non ha ancora risposto...
Perchè quello che non capisco è come usare Fermat dato che il teorema recita:
$a^(p-1) \equiv (1 mod p)$
ma io ho $z^73$ e $mod 37$ ....quindi le mie "p" non sono uguali...
Ho mandato una mail alla prof ma non ha ancora risposto...
Perchè quello che non capisco è come usare Fermat dato che il teorema recita:
$a^(p-1) \equiv (1 mod p)$
ma io ho $z^73$ e $mod 37$ ....quindi le mie "p" non sono uguali...
"pol20":
Non riesco ad andare fuori...
Ho mandato una mail alla prof ma non ha ancora risposto...
Perchè quello che non capisco è come usare Fermat dato che il teorema recita:
$a^(p-1) \equiv (1 mod p)$
ma io ho $z^73$ e $mod 37$ ....quindi le mie "p" non sono uguali...
Penso che in questo caso si debba usare il teorema di Eulero-Fermat: se $a$ e $b$ sono comprimi allora $a^(phi(b)) \equiv (1 mod b)$, dove $phi(b)$ è la funzione di Eulero che associa a $b$ il numero di naturali minori di $b$ e coprimi con $b$.
Sappiamo che $MCD(z,37)=1$ allora $z^(phi(37))\equiv (1 mod 37)$. Ma essendo 37 primo abbiamo che $phi(37)=37-1=36$, dunque $z^36 \equiv (1mod37)$.
A questo punto notiamo che $73=2*36 + 1$, dunque $z^73= z^(2*36+1) = (z^36)^2*z$. Considerando quanto affermato in precedenza abbiamo quindi che $z^73mod37 = ((z^36)^2*z)mod37= zmod37$.
Questo è quello che sono riuscito a ricavare, non so però se sia sufficiente ai fini della risoluzione dell'esercizio..
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo