# Thread: Find all positive integers less than 50 which divide 5^29 − 1

1. ## Find all positive integers less than 50 which divide 5^29 − 1

I can show that if q is a prime number which divides x=5^29−1, then either q is 2 or q ≡ 1 mod 29.

So the only prime <50 which divides x is 2. The numbers I need to check for divisibility are powers of 2 up to 32.

I think I can show that x is div. by 4 using divisibility laws and the fact that x is congruent to 24 mod 25 but I'm sure there's a better way.

Can anyone help?

2. Originally Posted by Josh146
I can show that if q is a prime number which divides x=5^29−1, then either q is 2 or q ≡ 1 mod 29.

So the only prime <50 which divides x is 2. The numbers I need to check for divisibility are powers of 2 up to 32.

I think I can show that x is div. by 4 using divisibility laws and the fact that x is congruent to 24 mod 25 but I'm sure there's a better way.

Can anyone help?
So the only prime less than $\displaystyle 50$ that divides $\displaystyle x$ is $\displaystyle 2$. So all we need to check are the powers of $\displaystyle 2$.

Let's look at $\displaystyle x$ modulo $\displaystyle 4$: $\displaystyle x=5^{29}-1\equiv1^{29}-1=0 \bmod{4}$. So $\displaystyle 4\mid x$.

Let's look at $\displaystyle x$ modulo $\displaystyle 8$: Note that $\displaystyle 5^2\equiv 1 \bmod{8}$, so $\displaystyle 5^{29}-1 = (5^2)^{14}\cdot5-1\equiv 4\not\equiv0\bmod{8}$.

Thus only $\displaystyle 2,4\mid x$ with regards to powers of $\displaystyle 2$. So $\displaystyle 2$ and $\displaystyle 4$ (and $\displaystyle 1$) are the only numbers less than $\displaystyle 50$ to divide $\displaystyle x$.

3. As an alternative, factorize $\displaystyle 5^{29} - 1$ (done using msieve here) :

$\displaystyle 5^{29} - 1 = 2 \times 2 \times 59 \times 35671 \times 22125996444329$

The solution to your problem trivially follows