Decompose $5^{1985} - 1$ into factors

Question

Decompose the number $5^{1985} - 1$ into a product of three integers, each of which is larger than $5^{100}$ .

We first notice the factorization $x^{5} - 1 = (x - 1) (x^{4} + x^{3} + x^{2} + x + 1)$ . Now to factorize $x^{4} + x^{3} + x^{2} + x + 1$ we get

(x^{2} + a x + 1) (x^{2} + b x + 1) = x^{4} + (a + b) x^{3} + (a b + 2) x^{2} + (a + b) x + 1 = x^{4} + x^{3} + x^{2} + x + 1

implies

a + b = 1, a b + 2 = 1

. Thus,

x^{4} + x^{3} + x^{2} + x + 1 = (x^{2} + (\frac{1 + \sqrt{5}}{2}) x + 1) (x^{2} + (\frac{1 - \sqrt{5}}{2}) x + 1) .

Is it possible to continue from this approach because now the factors I have aren't integers or is there a better way?

what made you come to this question? is it an excercise from a book? — Max
– Max, Commented Jul 20, 2016 at 20:55
@almagest Do you mean like $x^{5} - 1 = (x^{4} + a x^{3} + b x^{2} + c x + 1) x$ ? — user19405892
– user19405892, Commented Jul 20, 2016 at 21:00
One factor is $5^{397} - 1$ . But according to Wolfram Alpha, The remaining factors are $2^{2}$ , $11$ , $71$ , $146891$ , $1043801929$ and $7768438039$ which unlikely fulfill all your requirements. — Ng Chung Tak
– Ng Chung Tak, Commented Jul 20, 2016 at 21:01
@NgChungTak According to Pari-GP, $(5^{397} - 1) / 4$ is not prime, so other factors can come from this number — egreg
– egreg, Commented Jul 20, 2016 at 21:05

Jyrki Lahtonen · Accepted Answer · 2016-07-20 21:43:18Z

18

I would try Aurifeuillian factorization here.

Let $f (x) = x^{4} + x^{3} + x^{2} + x + 1$ be the fifth cyclotomic polynomial. The Aurifeuillian stuff says that $f (5 x^{2})$ factors into a product as follows

f (5 x^{2}) = (25 x^{4} - 25 x^{3} + 15 x^{2} - 5 x + 1) (25 x^{4} + 25 x^{3} + 15 x^{2} + 5 x + 1) .

Call those two factors on the RHS

g_{1} (x)

and

g_{2} (x)

.

Your number is

\begin{aligned} 5^{1985} - 1 & = (5^{397} - 1) f (5^{397}) \\ = (5^{397} - 1) g_{1} (5^{198}) g_{2} (5^{198}), \end{aligned}

and this fits the bill.

edited Jul 20, 2016 at 21:43

answered Jul 20, 2016 at 21:39

Jyrki Lahtonen

144k31 gold badges313 silver badges753 bronze badges

I thought of Aurifeuillian factorization, but did not expect that this works here. Great solution!

Peter
– Peter

2016-07-20 21:42:08 +00:00
Commented Jul 20, 2016 at 21:42
I thought Aurifeullian not come from a proper name, did not know that is because of J.F.A. Aurifeuille which I hear for the first time. Thanks.

Ataulfo
– Ataulfo

2016-07-20 23:39:33 +00:00
Commented Jul 20, 2016 at 23:39
Nice answer, nice reference! (+1)

Markus Scheuer
– Markus Scheuer

2016-07-21 07:05:21 +00:00
Commented Jul 21, 2016 at 7:05

Add a comment |

Peter · Accepted Answer · 2016-07-20 21:25:18Z

3

See here

http://factordb.com/index.php?query=5%5E1985-1

for the partial factorization of $5^{1985} - 1$ . There are three factors with $200$ digits or more. No idea how the factors can be expressed. Multiply one of the factors with the smaller factors to get a decomposition of the desired form.

answered Jul 20, 2016 at 21:25

Peter

87.3k17 gold badges89 silver badges246 bronze badges

Add a comment |

Community · Accepted Answer · 2017-04-13 12:19:49Z

3

A low-tech solution. $1985 = 5 \cdot 397$ , and $Φ_{5} (x)$ is a palyndromic polynomial, decomposable as

\begin{matrix} (1) & {(x^{2} - \frac{x}{2} + 1)}^{2} - \frac{5}{4} x^{2} \end{matrix}

or as:

\begin{matrix} (2) & (x^{2} + 3 x + 1)^{2} - 5 x (x + 1)^{2} \end{matrix}

that with

x = 5^{397}

is the difference of two squares,

a^{2} - b^{2} = (a - b) (a + b)

, with both

a - b

and

a + b

being

> 5^{100}

. The claim hence follows from

\begin{matrix} (3) & 5^{5 \cdot 397} = (5^{397} - 1) \cdot Φ_{5} (5^{397}) . \end{matrix}

edited Apr 13, 2017 at 12:19

CommunityBot

1

answered Jul 20, 2016 at 23:43

Jack D'Aurizio

374k42 gold badges421 silver badges894 bronze badges

1

How do you go from ${(x^{2} - \frac{x}{2} + 1)}^{2} - \frac{5}{4} x^{2}$ to $(x^{2} + 3 x + 1)^{2} - 5 x (x + 1)^{2} ?$

user19405892
– user19405892

2016-07-21 00:02:27 +00:00
Commented Jul 21, 2016 at 0:02
Inspired guess.

Jack D'Aurizio
– Jack D'Aurizio

2016-07-21 00:03:35 +00:00
Commented Jul 21, 2016 at 0:03
Good job. Unless I'm mistaken, substituting $x = 5 t^{2}$ into $(2)$ leads to a difference of squares and exactly the Aurifeuillian factorization.

Jyrki Lahtonen
– Jyrki Lahtonen

2016-07-21 05:59:00 +00:00
Commented Jul 21, 2016 at 5:59

Add a comment |

Stack Exchange Network

Decompose $5^{1985} - 1$ into factors

3 Answers 3

You must log in to answer this question.

Linked

Hot Network Questions

Strictly Necessary Cookies

Performance Cookies

Functional Cookies

Targeting Cookies

Decompose 51985−151985−1 into factors

3 Answers 3

You must log in to answer this question.

Linked

Related

Hot Network Questions

Decompose $5^{1985} - 1$ into factors