Proving if $a$ is not a multiple of prime $p$, then an integer $b$ exists such that $p^b - 1$ is a multiple of $a$ I tried many approaches but none of them really worked I treated $p^b-1$ as a Geometric progression but it didn't work and that is about as far as I have been able to go I have no clue how to move forward
 A: In the group $(\mathbb Z_a^*,\times)$ since $p$ isn't a multiple of $a$ then $\gcd(p,a)=1$ and then $\overline p\in  \mathbb Z_a^*$ and let $b=o(\overline p)$ then 
$$\overline p^b=\overline 1\iff p^b-1\equiv 0 \mod a$$
A: Let $(a,m)=1$ and not necessarily prime. Then by Euler theorem you get :
$$
m^{\phi(a)}\equiv 1 \mod a\implies a\mid m^{\phi(a)}- 1
$$
where $\phi(a)$ is Euler phi function.
When $p$ is a prime and $a$ is not multiple of $p$, then $(a,p)=1$ and you use Euler theorem to say:
$$
p^{\phi(a)}\equiv 1 \mod a \implies a\mid p^{\phi(a)}-1.
$$
Now choose $b=\phi(a)$.

Let me give another more elementary proof of OP. If you have $(a,p)=1$, consider all numbers of the form $p^k$ for $k\in\mathbb N$:
$$
\{p,p^2,p^3,...\}
$$
This is an infinite set. But the remainder of each $p^k$ lies in the set $\{1,...,a-1\}$ which is finite. By Pigeon hole principle, there are $m$ and $n$, different, such that $p^m$ and $p^n$ have the same remainder. Suppose $m>n$. This means:
$$
p^m=q_1a+r, p^n=q_2a+r \implies\\
 p^m-p^n=(q_1-q_2)a \implies a\mid p^m-p^n=p^n(p^{m-n}-1)
$$
But then $(a,p^n)=1$ and hence $a\mid (p^{m-n}-1)$. You can choose $b=m-n$.
