problema sobre congruência II

[Walter R]

preciso estabelecer a seguinte fórmula:

Se a é é um número ímpar, então \(a^{2^{n}}\equiv 1(mod2^{n+2})\)

[Rui Carpentier]

É questão de aplicar o teorema do tociente de Euler:

\(a^{\phi (n)}\equiv 1 \mbox{ mod } n\) sempre que \(a\) for coprimo com \(n\), sendo \(\phi (n)\) o número de inteiros entre \(1\) e \(n\) que são coprimos em relação a \(n\).

Assim é só determinar \(\phi \left(2^{n+2}\right)\) e verificar que resulta.

[Walter R]

Obrigado novamente, Rui. Haveria alguma maneira de provar a fórmula utilizando apenas a teoria básica da congruência (sem apelar para o teorema em questão)?

[Rui Carpentier]

Obrigado novamente, Rui. Haveria alguma maneira de provar a fórmula utilizando apenas a teoria básica da congruência (sem apelar para o teorema em questão)?

Sim, de facto. Seja \(a=2k_1+1\) um número ímpar. Temos que \(a^2=4k_1^2+4k_1+1=8k_2+1\)*, logo \(a^4=(8k_2+1)^2=64k_2^2+16k_2+1=16k_3+1\). Podemos usar este raciocínio para demonstrar por indução que
\((2k+1)^{2^n}=2^{n+2}k'+1\) (ou seja \((2k+1)^{2^n}\equiv 1 (mod 2^{n+2})\)). É só ver que
\((2k+1)^{2^{n+1}}=\left((2k+1)^{2^n}\left)^2=(2^{n+2}k'+1)^2=2^{2n+4}k'^2+2^{n+3}k'+1=2^{n+3}k'+1\)**.

* note-se que \(k_1(k_1+1)\) é par.

**Caso não se veja: (2k+1)^{2^{n+1}}=\left((2k+1)^{2^n}\left)^2=(2^{n+2}k'+1)^2=2^{2n+4}k'^2+2^{n+3}k'+1=2^{n+3}k'+1