# 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 $50$ that divides $x$ is $2$. So all we need to check are the powers of $2$.

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

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

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

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

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

The solution to your problem trivially follows