Mostre que se \operatorname{mdc}(a, m)=1 e a \equiv b(\bmod m) então
(i) \operatorname{mdc}(b, m)=1,
(ii) o_{m}(a)=o_{m}(b).

Passo 1

O enunciado dá as seguintes hipóteses e pede duas coisas.
  • Hipóteses dadas:
    • \operatorname{mdc}(a,m)=1.
    • a\equiv b\pmod m.
  • O que o enunciado pede:
    • (i) Mostrar que \operatorname{mdc}(b,m)=1.
    • (ii) Mostrar que o_{m}(a)=o_{m}(b), onde o_{m}(x) denota a ordem multiplicativa de x módulo m, isto é, o menor inteiro positivo k tal que x^{k}\equiv 1\pmod m (quando esse k existe).

Passo 2

Definições e fatos básicos que vamos usar (explicados de forma simples):
  • Definição de congruência: a\equiv b\pmod m significa que m divide a-b, isto é, existe k\in\mathbb{Z} com b=a+km.
  • Definição de \operatorname{mdc}(x,y): o maior inteiro positivo que divide simultaneamente x e y.
  • Propriedade útil sobre gcd (que vamos provar rapidamente): para todo k\in\mathbb{Z},
    \operatorname{mdc}(a,m)=\operatorname{mdc}(a+km,m).
    Esta propriedade é natural porque qualquer divisor comum de a e m divide a+km, e qualquer divisor comum de a+km e m divide a=(a+km)-km.
  • Ordem multiplicativa: para x com \operatorname{mdc}(x,m)=1, existe algum k>0 tal que x^{k}\equiv 1\pmod m. Uma razão rápida para a existência é o Teorema de Euler: se \operatorname{mdc}(x,m)=1 então x^{\varphi(m)}\equiv 1\pmod m, onde \varphi é a função totiente de Euler; assim a ordem o_m(x) é bem definida como o menor inteiro positivo com essa propriedade. Também usaremos que congruência é compatível com multiplicação e portanto com potências: se a\equiv b\pmod m então a^{n}\equiv b^{n}\pmod m para todo n\in\mathbb{N}.

Passo 3

Prova de (i): mostrar que \operatorname{mdc}(b,m)=1.
  • Como a\equiv b\pmod m, existe k\in\mathbb{Z} tal que b=a+km. Aplicando a propriedade mencionada: \operatorname{mdc}(b,m)=\operatorname{mdc}(a+km,m)=\operatorname{mdc}(a,m).
  • Pela hipótese \operatorname{mdc}(a,m)=1, segue imediatamente \operatorname{mdc}(b,m)=1.
  • Comentário didático curto: a igualdade da mdc entre a e a+km decorre do fato de que qualquer divisor comum de a e m divide a+km, e qualquer divisor comum de a+km e m divide a; portanto os conjuntos de divisores comuns são iguais, logo os maiores também.

Passo 4

Preparação para (ii): observar que as ordens o_m(a) e o_m(b) existem e que podemos comparar expoentes usando propriedades de congruência.
  • Pelo Passo 3 já sabemos \operatorname{mdc}(a,m)=\operatorname{mdc}(b,m)=1. Assim tanto o_m(a) quanto o_m(b) estão bem definidos como menores inteiros positivos tais que a^{o_m(a)}\equiv 1\pmod m e b^{o_m(b)}\equiv 1\pmod m.
  • Propriedade útil: se a\equiv b\pmod m então, por compatibilidade da congruência com multiplicação, para todo n\in\mathbb{N} vale a^{n}\equiv b^{n}\pmod m.(Isto pode ser mostrado por indução em n: caso base n=1 é dado; passo indutivo usa multiplicação.)

Passo 5

Mostrando que o_m(b) divide o_m(a).
  • Seja n=o_m(a). Então, por definição, a^{n}\equiv 1\pmod m.
  • Como a\equiv b\pmod m, aplicando a propriedade de potências: b^{n}\equiv a^{n}\equiv 1\pmod m.
  • Assim b^{n}\equiv 1\pmod m, o que mostra que a ordem de b é um divisor de n (pois a ordem é o menor expoente positivo que dá 1; todo expoente que dá 1 é múltiplo da ordem). Portanto o_{m}(b)\mid o_{m}(a).

Passo 6

Mostrando que o_m(a) divide o_m(b) (simetria do argumento).
  • Pelo mesmo raciocínio trocando os papéis de a e b: seja n'=o_m(b). Então b^{n'}\equiv 1\pmod m. Usando a\equiv b\pmod m e compatibilidade das potências obtemos a^{n'}\equiv b^{n'}\equiv 1\pmod m.
  • Logo o_m(a)\mid o_m(b).

Passo 7

Concluir (ii) a partir das divisibilidades mútuas.
  • Das duas divisibilidades obtidas nos Passos 5 e 6 temos o_{m}(b)\mid o_{m}(a)\quad\text{e}\quad o_{m}(a)\mid o_{m}(b),o que implica que o_{m}(a)=o_{m}(b).
  • Observação final: usamos essencialmente que congruência respeita potências e que a ordem é o menor expoente positivo que produz 1 módulo m. Também foi necessário garantir que as ordens existem, o que se dá porque \operatorname{mdc}(a,m)=1 (e assim \operatorname{mdc}(b,m)=1) e então existe algum expoente (por exemplo \varphi(m)) que leva à unidade módulo m.

Resposta

(i) \operatorname{mdc}(b,m)=1
(ii) o_{m}(a)=o_{m}(b)

Exercícios relacionados