North Macedonia

Let $p$ be the least prime factor of $b$, and $q$ be the least natural number such that $p\mid (a^q-1)$ (such a number exists because $p\mid (a^b-1)$). From Little Fermat's theorem, we have that $p\mid (a^{p-1}-1)$, which implies $q\mid b$ and $q\mid (p-1)$, and from the minimality of $p$, we get that $q=1$, i.e. $p\mid (a-1)$. Let $b=p^{\alpha }c$, where $c$ is not divisible by $p$. If $p^2\mid (a-1)$, then $a\equiv 1(\mathrm{mod}{p}^2)$, so $a^k\equiv 1(\mathrm{mod}{p}^2)$, for every natural number $k$ from $(a^{l(p-1)}+a^{l(p-2)}+\cdots +1)\equiv p(\mathrm{mod}{p}^2)$ and $(a^{p^{\alpha }(c-1)}+a^{p^{\alpha }(c-2)}+\cdots +1)\equiv c(\mathrm{mod}{p}^2)$, $a^{p^{\alpha }c}-1=(a-1)(a^{p-1}+a^{p-2}+\cdots +1)\dots$ $\dots (a^{p^{\alpha -1}}(p-1)+a^{p^{\alpha -1}}(p-2)+\cdots +1)(a^{p^{\alpha }(c-1)}+a^{p^{\alpha }(c-2)}+\cdots +1)$ so the degree of $p$ in $\frac{a^b-1}{a-1}$ is $\alpha$ and therefore we get that $p^{\alpha (a-1)}\mid (a-1)$ $(p^{\alpha a}\mid (a^b-1))$. The last is not possible because for $\alpha \ge 1$, $p\ge 2$ and $a\ge 2$, it holds that $p^{\alpha (a-1)}>a-1$.

This implies that, the degree of $p$ in $a-1$ must be $1$. If $p>2$, we will prove that the degree of $p$ in $a^{p^k}-1$ is $k+1$, for every natural number $k$. For $k=0$, the statement is true. Let the statement be true for every $k<n$. For $k=n$ from the following equalities $$a^{p^n}-1=(a^{p^{n-1}}{)}^p-1=(a^{p^{n-1}}-1)(a^{p^{n-1}(p-1)}+a^{p^{n-1}(p-2)}+\cdots +1)$$ and $$a^{l{p}^{n-1}}-1=(a^{p^{n-1}}-1)(a^{p^{n-1}(l-1)}+a^{p^{n-1}(l-2)}+\cdots +1)\equiv p^n{d}_{n}l(\mathrm{mod}{p}^{n+1})$$ we get that $$\begin{array}{rl}{a}^{p^n}-1& \equiv p^n{d}_n\left(p^n{d}_n(p-1+p-2+\cdots +1)+p\right)\equiv \\ & \equiv p^{n+1}{d}_n\left(p^n{d}_n\frac{p-1}{2}+1\right)(\mathrm{mod}{p}^{2n+1})\end{array}$$ (where $d_n=\frac{a^{p^{n-1}}-1}{p^n}$ and $d_n$ and $p$ coprime by the assumption) with which we've proved the statement by induction. From the equality $$a^{p^{\alpha }c}-1=(a^{p^{\alpha }}-1)(a^{p^{\alpha }(c-1)}+a^{p^{\alpha }(c-2)}+\cdots +1)$$ and from $a^{p^{\alpha }(c-1)}+a^{p^{\alpha }(c-2)}+\cdots +1\equiv c(\mathrm{mod}p)$, we get that the degree of $p$ in $a^b-1$ is $\alpha +1$, and on the other hand it must be greater or equal to $\alpha a$, which is possible only for $\alpha =1$ and $a=2$, but this case is not possible because of $p\nmid (a-1)$.

Now, the case when $p=2$ remains. From the equality (the same as above for $p>2$) $$a^{2^{\alpha }c}-1=(a-1)(a+1)\dots (a^{2^{\alpha -1}}+1)(a^{2^{\alpha }(c-1)}+a^{2^{\alpha }(c-2)}+\cdots +1).$$ The fact that $c$ is odd implies that $a^{2^{\alpha }(c-1)}+a^{2^{\alpha }(c-2)}+\cdots +1$ is an odd number as a sum of an odd number of odd numbers ($a$ has to be odd, because $2|(a-1)$). From $2|(a-1)$ and $2|(a+1)$, we get that $4|(a^{2k}-1)$, for every natural number $k$, but this implies that $4$ is not a divisor of $a^{2k}+1$. This implies that the degree of $2$ in $\frac{a^b-1}{a^2-1}$ is $\alpha -1$, so because $2^{\alpha a}|(a^b-1)$, we get that $2^{\alpha (a-1)+1}|(a^2-1)$, and because $4$ can be a divisor of only one of $a+1$ and $a-1$, we get that $2^{\alpha (a-1)}\le a+1$, which is possible if and only if $\alpha =1$ or $a=3$. Let $r$ be the least prime factor of $c$, $c=r^{\beta }d$, $r$ and $d$ are coprime and $s$ is the least natural number for which $r|(3^s-1)$. This implies that $s|b$ and $s|(r-1)$ (the same as before for $p$). This is possible only if $s=1$ or $s=2$ (those are the only divisors of $b$, less than $r$). In both cases $r|(3^2-1)$, which is possible only for $r=2$, a contradiction with the choice of $r$. We get that the unique solution is $b=2$ and $a=3$ ($b^a=8=a^b-1$).