# Divisors of (X^a-1)/(X-1) x is an odd prime, a is odd integer

• May 26th 2012, 09:28 AM
oden
Divisors of (X^a-1)/(X-1) x is an odd prime, a is odd integer
When factoring a number like (37^3-1)/36 = 3*7*67, I've noticed that almost all have at least one prime factor larger than x (e.g. 67 > 37). I would like to know for what values of x,a are ALL of the prime factors of (X^a-1)/(X-1) less than X. For example (79^3-1)/78 = 3*7^2*43 and 43 < 79 so one example is x = 79, a = 3. My math education level is first year of high school so a transparent explanation, if possible, would be great. I understand basic congruences.
• Jun 1st 2012, 10:08 PM
skeptopotamus
Re: Divisors of (X^a-1)/(X-1) x is an odd prime, a is odd integer
Certainly. $\frac{x^a-1}{x-1}$ has the form $x^{a-1} + x^{a-2} + \cdots + x + 1$, correct? So what you're really asking for is the set of integers of the form

$\alpha = \sum_{i=0}^{n} x^n$

which are such that $\forall$ primes $p$, $p|\alpha$ $\Rightarrow$ $p < x$. This is not a high school level problem, particularly for U.S. students, but it is not beyond approach. Let me put it this way for you, which should lead you to the answer:

What you're trying to avoid is that there is a prime $p, p > x$ such that [ $1 \equiv a \pmod p$], [ $x \equiv b \pmod p$], $\dots$, [ $x^n \equiv n \pmod p$] where [ $a + b + \cdots n \equiv kp \equiv 0 \pmod p$]. So try looking at a few cases that solve the system of equations you're looking for them to solve and make a couple of hypotheses (although it should be moderately apparent, and if not, the OEIS is always a good tool, if it wouldn't feel too much like cheating. But don't only look at primes for values of $x$ or you will not find the sequence!). You will find that there is a certain class of numbers that admits the property which you seek, and a proof by contradiction follows without too much trouble. It is a much easier problem algebraically than when using strictly elementary tools, but I see how to go about it using only elementary techniques. Another hint: Ignore the '1' and try to avoid [ $b + c + \cdots n \equiv p-1 \equiv -1 \pmod p$].

The proof is not short, but I will come back in a week or two and write it out for you if you still have not come up with the solution.