Resposta: Podemos provar que o MDC[A^(m) – 1, A^(n) – 1] = MDC(m, n) – 1 utilizando a propriedade da congruência e algumas propriedades do MDC. Aqui está uma possível prova:
Explicação passo a passo:
Seja d = MDC[A^(m) – 1, A^(n) – 1]. Sabemos que d | A^(m) – 1 e d | A^(n) – 1, o que implica que A^(m) ≡ 1 (mod d) e A^(n) ≡ 1 (mod d).
Se A^(m) ≡ 1 (mod d) e A^(n) ≡ 1 (mod d), então A^(MDC(m, n)) ≡ 1 (mod d), pois MDC(m, n) é o menor número inteiro que é múltiplo tanto de m quanto de n. (Esta é uma propriedade da congruência e pode ser demonstrada usando o Teorema de Bézout).
Portanto, MDC[A^(m) – 1, A^(n) – 1] = d | A^(MDC(m, n)) – 1. Isso implica que MDC(m, n) divide MDC[A^(m) – 1, A^(n) – 1] + 1. (Esta é outra propriedade da congruência, que pode ser demonstrada usando o Teorema de Bézout).
Agora, vamos provar que MDC(m, n) – 1 divide MDC[A^(m) – 1, A^(n) – 1]. Podemos fazer isso mostrando que MDC(m, n) – 1 é um divisor comum de A^(m) – 1 e A^(n) – 1, e que é maior ou igual a qualquer outro divisor comum. (Isso é uma propriedade do MDC).
Seja k = MDC(m, n) – 1. Sabemos que k | m e k | n, o que implica que A^(m) ≡ 1 (mod k) e A^(n) ≡ 1 (mod k).
Então, A^(MDC(m, n)) ≡ 1 (mod k), pois MDC(m, n) é um múltiplo comum de m e n.
Além disso, sabemos que k é um divisor comum de A^(m) – 1 e A^(n) – 1, pois k | m e k | n implicam que A^(m) – 1 ≡ A^(n) – 1 ≡ 0 (mod k).
Portanto, k é um divisor comum de A^(m) – 1 e A^(n) – 1 que é maior ou igual a qualquer outro divisor comum. Isso implica que k = MDC[A^(m) – 1, A^(n) – 1].
que está incorreta!! Pois mdc(A²-1, A-1) = A-1. Eu acredito que o enunciado desejado para essa questão é [tex]\textrm{mdc }\!( A^m - 1, A^n - 1) =A^{\textrm{mdc }\!(m,n)} -1[/tex]
onde m,n são naturais e A é maior ou igual a 2. Por exemplo, é verdade que [tex]\textrm{mdc }\!( A^6 - 1, A^4 - 1) =A^{\textrm{mdc }\!(6,4)} -1 = A^2 - 1[/tex]
Pra provar isso, sem perda de generalidade suponha que m > n. Sendo m = nq + r, da identidade
Lista de comentários
Resposta: Podemos provar que o MDC[A^(m) – 1, A^(n) – 1] = MDC(m, n) – 1 utilizando a propriedade da congruência e algumas propriedades do MDC. Aqui está uma possível prova:
Explicação passo a passo:
Seja d = MDC[A^(m) – 1, A^(n) – 1]. Sabemos que d | A^(m) – 1 e d | A^(n) – 1, o que implica que A^(m) ≡ 1 (mod d) e A^(n) ≡ 1 (mod d).
Se A^(m) ≡ 1 (mod d) e A^(n) ≡ 1 (mod d), então A^(MDC(m, n)) ≡ 1 (mod d), pois MDC(m, n) é o menor número inteiro que é múltiplo tanto de m quanto de n. (Esta é uma propriedade da congruência e pode ser demonstrada usando o Teorema de Bézout).
Portanto, MDC[A^(m) – 1, A^(n) – 1] = d | A^(MDC(m, n)) – 1. Isso implica que MDC(m, n) divide MDC[A^(m) – 1, A^(n) – 1] + 1. (Esta é outra propriedade da congruência, que pode ser demonstrada usando o Teorema de Bézout).
Agora, vamos provar que MDC(m, n) – 1 divide MDC[A^(m) – 1, A^(n) – 1]. Podemos fazer isso mostrando que MDC(m, n) – 1 é um divisor comum de A^(m) – 1 e A^(n) – 1, e que é maior ou igual a qualquer outro divisor comum. (Isso é uma propriedade do MDC).
Seja k = MDC(m, n) – 1. Sabemos que k | m e k | n, o que implica que A^(m) ≡ 1 (mod k) e A^(n) ≡ 1 (mod k).
Então, A^(MDC(m, n)) ≡ 1 (mod k), pois MDC(m, n) é um múltiplo comum de m e n.
Além disso, sabemos que k é um divisor comum de A^(m) – 1 e A^(n) – 1, pois k | m e k | n implicam que A^(m) – 1 ≡ A^(n) – 1 ≡ 0 (mod k).
Portanto, k é um divisor comum de A^(m) – 1 e A^(n) – 1 que é maior ou igual a qualquer outro divisor comum. Isso implica que k = MDC[A^(m) – 1, A^(n) – 1].
Assim, MDC[A^(m) – 1, A^(n) – 1] = MDC(m, n) – 1, como queríamos demonstrar.
Portanto, provamos que o MDC[A^(m) – 1, A^(n) – 1] = MDC(m, n) – 1.
Verified answer
Olá, não é possível provar que
[tex]\textrm{mdc }\!( A^m - 1, A^n - 1) =\textrm{mdc }\!(m,n) -1[/tex]
Pois essa igualdade é falsa. Por exemplo, para m = 2 e n = 1 teríamos
[tex]\textrm{mdc }\!( A^2 - 1, A^1 - 1) =\textrm{mdc }\!(2,1) -1 = 0[/tex]
que está incorreta!! Pois mdc(A²-1, A-1) = A-1. Eu acredito que o enunciado desejado para essa questão é
[tex]\textrm{mdc }\!( A^m - 1, A^n - 1) =A^{\textrm{mdc }\!(m,n)} -1[/tex]
onde m,n são naturais e A é maior ou igual a 2. Por exemplo, é verdade que
[tex]\textrm{mdc }\!( A^6 - 1, A^4 - 1) =A^{\textrm{mdc }\!(6,4)} -1 = A^2 - 1[/tex]
Pra provar isso, sem perda de generalidade suponha que m > n. Sendo m = nq + r, da identidade
[tex]B^q - 1 = (B-1)(1+B+B^2 + \cdots + B^{q-1})[/tex]
para [tex]B = A^n[/tex] segue que [tex]A^n-1[/tex] divide [tex]A^{nq}-1[/tex]. Portanto
[tex]\textrm{mdc }\!( A^m - 1, A^n - 1) =\textrm{mdc }\!( A^r (A^{nq}-1) + A^r -1, A^n-1)= \textrm{mdc }\!(A^r-1, A^n-1)[/tex]
Ou seja, trocamos (m,n) por (n,r) Pelo algoritmo de Euclides, segue que realizando divisões sucessivas, obteremos
[tex]\textrm{mdc }\!(A^m-1, A^n - 1) = A^{\textrm{mdc }\!(m,n)} -1[/tex]