Problema com inverso multiplicativo modular.

Question

Estou tentando o meu melhor para resolver um dos meus exercícios do exame preparatório. Tenho uma tese que parece certa (verifiquei em pequenos números), mas não posso provar .... Então aqui está:$x \perp n $ e $x+1 \perp n.\, $ Deixei $\,x' = x^{-1}\bmod n.\,$ Provar que $ x' \perp n $ e $ x' + 1 \perp n $. Primeira parte com$ x' \perp n $é fácil, mas em segundo lugar, não posso provar. Obrigado por toda ajuda!

Answer 1

Embora provável pela manipulação das equações de Bezout, isso obscurece a estrutura aritmética no cerne da questão - que$\color{#c00}{\text{divisors}}\!$ $\!\color{#0a0}{\text{ of invertibles remain invertible}}$. Vamos trazer isso à tona.

Bezout lembra que$\,a$ é invertível $\!\bmod n\iff a\,$ é coprime para $n.\,$ Aplicar isso abaixo produz

$\!\bmod n\!:\ a$ é invertível $\Rightarrow aa^{-1}\equiv 1$ então $a^{-1}$ é invertível (com o inverso $\equiv a)$ então $a^{-1}$ é coprime para $n$

Além disso, observe se $\,a \equiv \color{#c00}b\,c\,$ então $\,1 \equiv aa^{-1} \equiv b(ca^{-1})$ então $\,\color{#c00}b\,$ é $\color{#0a0}{\text{also invertible}}$ (com inverso $ca')$.

Tão invertível $\ x+1 \equiv (\color{#c00}{1+x^{-1}})x\,\Longrightarrow\,$ invertível $\,\color{#c00}{1+x^{-1}}.\,$ Portanto, ambas as afirmações são óbvias dessa forma.

Observação $ $ A primeira reivindicação também pode ser deduzida desta forma, ou seja, $\,aa^{-1}\equiv 1\,$ então $\,a^{-1}$ é um divisor do invertível $1$ portanto, permanece invertível.

Assim, o conjunto de invertíveis é fechado sob divisores e produto. Essa estrutura algébrica é conhecida como monóide saturado e é muito útil na teoria dos números.

Answer 2

Vamos denotar $a=x \ mod^{-1} \ n$. Existe$b$ de tal modo que $ax + bn = 1$. Isso é claro, por Bezout, que$gcd(a,n)=1$.

Para a segunda parte agora, por hipótese existe $c,d$ de tal modo que $c(x+1)+dn=1$. Então um tem$$ (a+1)cx + (bc+d)n = c(ax + bn) + cx + dn = c + 1-c = 1$$ então $gcd(a+1,n)=1$.