I'm trying, but struggling, to prove this statement about congruences. The title is perhaps uniformative, which I apologize for, so feel free to edit or comment if you have a better description.

Theorem: Let $p$ and $r$ be distinct primes greater than $2$. Then, $p^{r-1} + r^{p-1} \equiv 1 \ \text{(mod $pr$)}$.

Here's my best attempt at a proof. It doesn't get 'prove' it, but rather gives a string of facts I was able to piece together which, unless I missed something important, may be sufficient to write the proof, but I'm struggling to piece them together correctly.

Proof Attempt:

Since $p$ and $r$ are prime, it's clear that they are relatively prime to one another, so $\gcd(p,r) = 1$. Thus, we are free to leverage faremont's theorem in considering $p^{r-1}$ and $r^{p-1}$.

From $p^{r-1}$, that $p$ and $r$ are relatively prime tells us that $p^{r-1} \equiv 1 \ \text{(mod $r$)}$. Similarly, we have $r^{p-1} \equiv 1 \ \text{(mod $p$)}$.

Now, by definition, we have, taking $p$ and $r$ as fixed: \begin{align*} p^{r-1} \equiv 1 \ \text{(mod $r$)} \iff \exists a \in \mathbb{Z}, p^{r-1} -1 = ar \end{align*} and \begin{align*} r^{p-1} \equiv 1 \ \text{(mod $p$)} \iff \exists b \in \mathbb{Z}, q^{r-1} - 1 = bp \end{align*} So, now I can't quite figure out how to string these together. We could add the two equations so that we have $p^{r-1} + r^{p-1}$ on the same side of an equation, but then we have a $-2$ term that we can't quite eliminate, nor we can we factor out $pr$ from the right-hand side of the equation, though we can factor out a $p$ from one term and an $r$ from another. The only other thing that occurred to me was that $p$ and $r$ being relatively prime implies invertibility. Similarly, that they have a $\gcd$ of $1$ means that we can write $1$ as a linear combination of $p$ and $r$ with integer coefficients, but that still didn't quite help with factoring out a $pr$ from the right-hand side, even if it seems to isolate $p^{r-1} + r^{p-1} - 1$ on one side of the equation.

I'd greatly appreciate any helpful comments or hints. I'd really like to figure as much of this out myself, as I'd like to think I'm reasonably close, so any guidance in the right direction is especially appreciated. I'll edit this question later, hopefully with an updated, correct proof of this and credit whoever provided any thoughts.



Are you familiar with the property

$a \equiv b \pmod{m_1}$

$a \equiv b \pmod{m_2}$


$a \equiv b \pmod{m_n}$

$\implies a \equiv b \pmod{\text{lcm}(m_1, m_2, \ldots, m_n)}$?

If not, try to prove it! This gives a direct solution to the problem you're facing. And I believe $p$ and $r$ must be distinct in order for this solution to work. Otherwise, I'm pretty sure $p^{r-1} + r^{p-1} \equiv 2 p^{p-1} \equiv 0 \not\equiv 1 \pmod{p^2}$.

  • $\begingroup$ I'm not familiar with it, but I'll work on it -- thank you! And, yes, I should have mentioned that $p$ and $r$ are distinct. I'll revise the original post with that. $\endgroup$ – Matt.P Aug 9 '18 at 22:52

$p^{r-1}+r^{p-1}=r^{p-1}=1\mod{p}$, and similarly $p^{r-1}+r^{p-1}=p^{r-1}=1\mod{r}$; so by the Chinese Remainder Theorem, the expression can only be $1\mod{pr}$ (as there can only be one residue $k$ modulo $pr$ that is equivalent to $1\mod{p}$ and $1\mod{r}$ by Chinese Remainder Theorem, and since $k=1$ is a solution, it is the only solution).

Without using CRT: the equations given earlier tell us that $p,r$ are both factors of $p^{r-1}+r^{p-1}-1$ (as $p^{r-1}+r^{p-1}$ is equivalent to $1$ modulo $p$ and $r$); thus $pr$ is a factor of $p^{r-1}+r^{p-1}-1$, so $p^{r-1}+r^{p-1}=1\mod{pr}$.

  • $\begingroup$ I cannot believe I didn't think of this. $p \equiv 0 \ \text{(mod $p$)}$, so clearly $p^{r-1} \equiv 0$. I'm not familiar with the Chinese remainder theorem, so I will need to look into this. But this is extremely helpful. Thank you. $\endgroup$ – Matt.P Aug 9 '18 at 22:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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