Question on divisibility of a prime raised to power $b-1$. Suppose $a$ is a natural number which is not a multiple of prime $b$. Then prove that there exists a natural number $b$ such that $p^b-1$ is a multiple of $a$. 
I have tried formulating it and arrived at 
$b = log_p(a(n)+1)$
How to prove that there are solutions to this equation?
 A: Consider the powers of $p$ and their remainders when divided by $a$.
Since there are only finitely many possible reminders between $0$ and $a$, two powers of $p$ must leave the same remainder: $p^{n+b}$ and $p^n$.
This implies that $a$ divides $p^{n+b}-p^n=p^n(p^b-1)$.
Since $a$ and $p$ are coprime, we must have that $a$ divides $p^b-1$.
A: I need to write this as
$n^b-1 \equiv 0 \pmod a$
$n^b \equiv 1 \bmod a$

Euler's theorem:
Let $n$ and $a$ be coprime. Then $n^{\varphi(a)} \equiv 1 \pmod a$ where $\varphi(a)$ is the value of the Euler phi function evaluated at $a$.

In other words, all you need is for $a$ and $n$ to be coprime. $n$ does not need to be a prime number. 
The Euler phi function evaluated at $a$ is written $\varphi(a)$ and is equal to the number of integers in the set $\{1,2,3,\dots, a\}$ that are coprime to $a$.
If $p$ is a prime number and $r$ is a positive integer, then $\varphi(p^r) = p^r - p^{r-1}$.
If $\displaystyle N = \prod_{i=1}^m p_i^{r_i}$ is a product of powers of distinct prime numbers, then
$\displaystyle \varphi(N) = \prod_{i=1}^m \varphi\left(p_i^{r_i}\right)$
For example. Let $n=7$ and $a = 36= 2^2 \cdot 3^2$.
$\varphi(36) = \varphi(4) \cdot \varphi(9) = (4-2)(9-3) = 12$.
Then $7^{12}-1=13841287200 = 36\cdot384480200$.
I should mention that $\varphi(a)$ may not be the smallest possible answer. If there is a smaller answer, though, it must be a divisor of $\varphi(a)$
In the above example $7^6-1 = 36\cdot2368$
A: Here is a funny solution. Consider the fraction $1/a$ and its radix $p$ periodic expansion $0.(b_1b_2\dotsm b_n)$. Then, by the standard rules (that also hold in radix $p$),
$$
\frac{1}{a}=\frac{x}{p^n-1}
$$
where $x=b_1b_2\dotsm b_n$ (the right hand side means the radix $p$) expansion. There is no antiperiod, because $a$ is not divisible by $p$.
Then $ax=p^n-1$.

This extends to any radix $b$; if $\gcd(a,b)=1$, then there exists $n>0$ such that $a$ divides $b^n-1$.
A: For any p greater than 2 and b greater than 1, (p^b)-1 is divisible by p-1. Of course if p is 2 then (p^b)-1 might be prime. As long as p is not 2 then a value for b exists and a=p-1 since p-1 is coprime to p and (p^b)-1 is a multiple of p-1. If p=2 then there will be some power of 2 minus 1 which is not prime but will be an odd number, so it is divisible by an odd number and all odd numbers greater than 1 are coprime to 2. For example 2^9-1=511 is divisible by 7 which is coprime to 2. I am surprised that this question included the prime number 2, if the question had been phrased as "p is an odd prime" then an easy answer is a=p-1 and b can be any integer greater than 1.
