If $p\nmid a$ (where $p$ is a prime), then prove that there is an integer $b$ such that $a\mid (p^b -1)$ 
If $p\nmid a$ (where $p$ is a prime), then prove that there is an integer $b$ such that $a\mid (p^b -1)$ . 

Though the thing seems easily verified through trivial put and check solutions, but I am not being able to get a complete solution as per required in number theory. Please help and kindly give suggestion on how I can improve my number theory...
 A: Observe that since $p\nmid a$ we can say that $\gcd(a,p)=1$. It immediately follows from Euler's Theorem  that, $$p^{\varphi(a)}\equiv 1\pmod a$$ where $\varphi$ is Euler's Totient Function.
A: For each of the powers $p^1$, $p^2$, $p^3$, $p^4$, and so on, imagine computing the remainders when $p^1$, $p^2$, $p^3$, $p^4$, and so on is divided by $a$. 
There are only finitely many conceivable different remainders, so there are positive integers $k$ and $l$, with $k\lt l$, such that $p^l$ has the same remainder on division by $a$ as $p^k$. 
It follows that $p^l-p^k$ is divisible by $a$, and therefore $p^k(p^{l-k}-1)$ is divisible by $a$.
However, $p^k$ is relatively prime to $a$, so $a$ must divide $p^{l-k}-1$. Set $b=l-k$, and we are finished. 
A: 
$a|p^b-1$.

So, we can say,$p^b\equiv1\pmod a$
From Euler phi function,we get
$p^{\phi(a)}\equiv1\pmod a$ $
$[\phi(a)=\text{number of integers less than and co-prime to 'a'}]$.If $a=p_1^a\times p_2^b...p_n^z$ is the prime factorisation of $a$ then $\phi(a)=a(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_n})$
Comparing the two equations we get,$b=\phi(a)$
