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

1. ## 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.

2. ## 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.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 16, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "http://mathhelpforum.com/number-theory/199303-divisors-x-1-x-1-x-odd-prime-odd-integer.html", "fetch_time": 1480895104000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2016-50/segments/1480698541426.52/warc/CC-MAIN-20161202170901-00199-ip-10-31-129-80.ec2.internal.warc.gz", "warc_record_offset": 182792131, "warc_record_length": 10757, "token_count": 665, "char_count": 2228, "score": 4.21875, "int_score": 4, "crawl": "CC-MAIN-2016-50", "snapshot_type": "longest", "language": "en", "language_score": 0.9314078092575073, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00020-of-00064.parquet"}