2
$\begingroup$

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$

  • 1
    I have retracted the -1, this is about showing $\beta$ is odd, which is a different problem. Unfortunately cannot retract the close vote. Apologies.2011-04-07

2 Answers 2

1

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.

1

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.