# 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?

• Hints. Step 1: Show that there exist positive integers $i>j$ such that $p^i$ and $p^j$ leave the same remainder when divided by $a$. Step 2: Show that $b=i-j$ works. – Jyrki Lahtonen Sep 13 '17 at 10:26
• In this exercise the tools your should primarily think about are based on divisibility. The concept of a prime number is about the same theme, and solution is likely to also go there. Full credit for trying to think outside that box, but using logarithms like in your attempt is unlikely to work here (but tools from elsewhere may be the key to success in some other problem). – Jyrki Lahtonen Sep 13 '17 at 10:32

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$.

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$

• I think the question was looking for $a \mid p^b-1$. – David K Sep 13 '17 at 10:43
• @DavidK Thank you. My brain has been on vacation lately. I think I have fixed the problem now. – steven gregory Sep 13 '17 at 11:31
• Indeed, I think that's the answer. – David K Sep 13 '17 at 11:36

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$.

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.