Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$$

share|cite|improve this question
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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.