# Prove that $(n-1) = (n - 1)^{\beta} \pmod{n}$ when $n$ is even

Let $\alpha$, $1 \lt \alpha \lt \varphi(n)$, $\gcd(\alpha, \varphi(n)) = 1$, and $\beta \equiv \alpha^{-1} \pmod {\varphi(n)}$, where $\varphi$ is Euler's totient function.

When n is even, how would I prove:

$$(n-1) \equiv (n - 1)^{\beta} \pmod n$$

-
you already got an answer in your previous question - it's the parity of $\beta$ who decides – user8268 Apr 7 '11 at 14:42
Instead of asking how would I prove, it would be better to say what you have tried. – picakhu Apr 7 '11 at 14:50
I have retracted the -1, this is about showing $\beta$ is odd, which is a different problem. Unfortunately cannot retract the close vote. Apologies. – Aryabhata Apr 7 '11 at 15:02

The $(n-1)$ and $mod ~ n$ are, in some sense, red herrings. As user8268 notes above, it suffices to show that $\beta$ is odd when $n\geq 3$. When $n = 2$, $(-1)^k = 1^k = 1 = -1 mod ~2$ for any $k$, so there's nothing to prove.

To show that $\beta$ is odd, it suffice to note that the Euler totient $\varphi(n)$ is even for any $n\geq 3$. Using that $\alpha$ and $\varphi(n)$ is coprime by assumption, you have that $\alpha$ and hence $\beta$ are both odd.

-

If ring $\rm\:Z\:$ (e.g. integers) contains $\rm\:n\:$ and all coefficients of polynomial $\rm\:f(x)\:$ then we map apply

FACTOR THEOREM $\rm\ \ \ n\ |\ f(n)\ \iff\ n\ |\ f(0)\quad\$ where $\rm\ n\ |\ m\$ means $\rm\: k\ n\: = m\$ for some $\rm\ k\in Z$

Therefore $\rm\ \ n\ |\ (n-1)^b-(n-1)\ \iff\ n\ |\ (-1)^b + 1\$

So for odd $\rm\:b\:$ it is $\rm\:n\ |\ 0\:,\:$ which is always true; for even $\rm\:b\:$ it is $\rm\:n\ |\ 2\:,\:$ which may be true or false.

-