1. ## Divisiblility

Find all$\displaystyle (a,b)$,
where a is a prime number, $\displaystyle 2a \geq b$

such that

$\displaystyle (a-1)^b+1 \equiv 0 \bmod b^{a-1}$

2. First consider $\displaystyle a > 2$

In this case we have: $\displaystyle \left( {a - 1} \right)^b + 1$ odd, thus $\displaystyle b$ is odd.

The case $\displaystyle b=1$ is trivial, so consider $\displaystyle b>1$

Let $\displaystyle p = \min \left\{ {x \in \mathbb{Z}^ + /x \ne 1 \wedge \left. x \right|b} \right\}$ this turns out to be the smallest prime dividing $\displaystyle b$

Now: $\displaystyle \left( {a - 1} \right)^b + 1 \equiv 0\left( {\bmod .b^{a - 1} } \right) \Rightarrow \left( {a - 1} \right)^b \equiv - 1\left( {\bmod .p} \right){\text{ (*)}}$$\displaystyle \Rightarrow \left( {a - 1} \right)^{2b} \equiv 1\left( {\bmod .p} \right){\text{ (**)}}$

Let $\displaystyle t = {\text{ord}}_{\text{p}} \left( {a - 1} \right) \Rightarrow \left. t \right|\left( {2b} \right)$ because of $\displaystyle {\text{(**)}}$ and we also have $\displaystyle \left. t \right|\left( {p - 1} \right)$ (by Fermat's Little Theorem)

Thus $\displaystyle \left. t \right|{\text{gcd}}\left( {2b,p - 1} \right)$ and note that: $\displaystyle {\text{gcd}}\left( {2b,p - 1} \right) = 2 \Rightarrow \left. t \right|2 \Rightarrow \left( {a - 1} \right)^2 \equiv 1\left( {\bmod .p} \right)$ that is $\displaystyle p\left| {\left[ {\left( {a - 1} \right)^2 - 1} \right]} \right.$ and using Euclid's Lemma we get: $\displaystyle \left. p \right|a{\text{ OR}}\left. {{\text{ }}p} \right|\left( {a - 2} \right)$

If we had: $\displaystyle \left. {{\text{ }}p} \right|\left( {a - 2} \right) \Rightarrow \left( {a - 1} \right)^b \equiv \left( 1 \right)^b \equiv 1\left( {\bmod .p} \right)$, contradicting $\displaystyle \text{(*)}$ $\displaystyle \Rightarrow \left. p \right|a \Rightarrow p = a \Rightarrow \boxed{\left. a \right|b}$

Now since $\displaystyle 2a\geq{b}$ it follows that we have $\displaystyle b = 2a{\text{ or }}b = a$

If $\displaystyle b=a$ then $\displaystyle a^{a - 1} \left| {\left[ {\left( {a - 1} \right)^a + 1} \right]} \right.$ and expand $\displaystyle \left( {a - 1} \right)^a + 1$ by using the Binomial Theorem: $\displaystyle \left( {a - 1} \right)^a + 1 = \binom{a}{1}\cdot a - \binom{a}{2}\cdot a^2 \pm ...$ and note that $\displaystyle a|\binom{a}{k}$ for all $\displaystyle 0<k<a$ thus $\displaystyle a^2\left| {\left[ {\left( {a - 1} \right)^a + 1} \right]} \right.$ but note that $\displaystyle \tfrac{{\left( {a - 1} \right)^a + 1}} {{a^2 }} \equiv 1\left( {\bmod .a} \right)$ thus $\displaystyle a-1\leq 2$ thus $\displaystyle a=3$ and we get the solution $\displaystyle (a,b)= {\left( {3,3} \right)}$

If $\displaystyle b=2a$ we find that $\displaystyle a\not| \left[ {\left( {a - 1} \right)^{2a} + 1} \right]$ hence this generates no solutions.

Now it only remains to check what happens when $\displaystyle a=2$, here we have $\displaystyle \left( {a - 1} \right)^b + 1 = 2$ and so $\displaystyle b=1$ or $\displaystyle b=2$.

Thus the solutions are $\displaystyle \left( {a,1} \right)\forall a\in\mathbb{Z^{+}};\left( {2,2} \right);\left( {3,3} \right)$