# Inspired by Jihoon Kang

Prove or disprove that the following number is prime:

$\frac{ 16 ^ {125} - 1 } { 16 ^ {25} -1 }$

Inspiration

Note by Calvin Lin
5 years, 10 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

Let $a=16^{25}$, then the number is $\dfrac{a^5-1}{a-1}=1+a+a^2+a^3+a^4\equiv 0(\mod{5})\ (\because a\equiv 1\mod {5})$ This shows that there is nothing sacrosanct about $16^{25}$ anything that has a remainder $1$ modulo 5 (in general $n$) will do.

- 5 years, 10 months ago

"Sacrosanct" is such a beautiful word. Well done, too.

- 5 years, 9 months ago

We see that $16^{125} = (15 + 1)^{125} = 1 + 15 \cdot 125 + 625(\ldots ) \equiv 1 \pmod {5^4} \Rightarrow 16^{125} - 1 \equiv 0 \pmod {5^4}$

And $16^{25} = (15 + 1)^{25} = 1 + 25 \cdot 15 + 125 (\ldots ) \equiv 1 \pmod {5^3} \Rightarrow 16^{25} - 1 \equiv 0 \pmod {5^3}$

But $16^{25} = (15 + 1)^{25} = 1 + 25 \cdot 15 + 625 (\ldots ) \equiv 376 \pmod {5^4} \Rightarrow 16^{25} - 1 \not \equiv 0 \pmod {5^4}$

So there's more powers of $5$ that divides the numerator than the denominator, thus the number is divisible by $5$.

- 5 years, 10 months ago

Alternatively, you could use Fermat's little theorem in Lines 1 and 2 (Line 2 is logically unnecessary, anyway): $16^{125}=2^{500}=2^{\phi(625)}\equiv1 (\mod 625)$ .

- 5 years, 10 months ago

Haha, nice! I post this in a rush without proofreading it! Obviously the simplest way is to do Samrat's way. By the way, it's Euler's totient function, not Fermat's little theorem.

- 5 years, 10 months ago

As a Swiss, I should be ashamed of myself to cite Fermat rather than my countryman Euler ;) I guess I was in a rush too...

- 5 years, 10 months ago

Obviously the number is an integer because letting $z = 25^5$, we get

\begin{aligned} && \frac {z^{25}-1}{z - 1} \\ &=& z^{24}+z^{23} + \ldots + z + 1 \\ &=& (z^{24} + z^{23} + z^{22} + z^{21} + z^{20} )\\ & \ & + (z^{19} + z^{18} + z^{17} + z^{16} + z^{15} ) \\ & \ & + (z^{14} + z^{13} + z^{12} + z^{11} + z^{10} ) \\ & \ & + (z^{9} + z^{8} + z^{7} + z^{6} + z^{5} ) \\ & \ & + (z^{4} + z^{3} + z^{2} + z^{1} + z^{0} ) \\ &=& (z^4 +z^3+z^2+z + 1)(1 + z^5 + z^{10} + z^{15} + z^{20} ) \\ \end{aligned}

Which is factorization of two integers, so it's not prime.

Note that with enough patience, one could show that it is divisible by $101$ by Fermat's little theorem and exponentiation by squaring but it's a little bit tedious.

- 5 years, 10 months ago

Oh ooops. Typo. Fixed!

The question has to be much more interesting than that ...

Staff - 5 years, 10 months ago

I just proved it, essentially the same proof as the earlier problem :). I won't spoil it for others. But I will leave a rather interesting hint:

Think about the square of a sum of the first 3 terms of a geometric progression, with the first term 1 and common ratio $16^{25}$

- 5 years, 10 months ago

That is a really nice proof for the earlier unedited version . Thank you for sharing that. What I really like about your proof is that it also proves the edited version :)

- 5 years, 10 months ago

One could also show that $\frac {9^{125}-1}{9^{25} - 1}$ is composite. Letting $x = 9^{25}$

It will simplify to this too: $x^4 + x^3 + x^2 + x + 1$

Using the algebraic identity

\begin{aligned} x^4 + x^3 + x^2 + x + 1 &=& (x^2 + x+ 1)^2 - x(x^2 + 2x + 1) \\ &=& (x^2 + x + 1)^2 - x(x+1)^2 \\ &= &(x^2 + x+ 1)^2 - 9^{25} (x+1)^2 \\ &=& (x^2 + x + 1)^2 - 3^{50} (x+1)^2 \\ &=& (x^2 + x + 1)^2 - (3^{25}(x+1))^2 \\ &=& (x^2 + x + 1 + 3^{25}(x+1)) (x^2 + x + 1 - 3^{25}(x+1)) \\ \end{aligned}

It can be easily shown that $(x^2 + x + 1 - 3^{25}(x+1)) \ne \pm 1$.

Because $(x^2 + x + 1 - 3^{25}(x+1))$ and $(x^2 + x + 1 + 3^{25}(x+1))$ are neither $\ \pm 1$, then their product is definitely not a prime number.

- 5 years, 10 months ago

You wrote : x^2 + 2 x + 1 instead of x^2 + x + 1 at the 4th line

- 5 years, 10 months ago

$x^4 + x^3 + x^2 + x + 1 = (x^2 + x+ 1)^2 - x(x^2 + 2x + 1)$ is correct.

- 5 years, 10 months ago

If I am not mistaken, any time 6 is multiplied by itself, the resulting number's last digit will always be six. Subtracting 1 will leave 5 as the last digit, and any integer with 5 as its last digit is divisible by 5. Please correct me if I am wrong, as I only come on this site to learn.

- 5 years, 10 months ago

OH MY GOODNESS THAT SAYS 16. IGNORE THE PREVIOUS COMMENT.

- 5 years, 10 months ago

1

- 5 years, 10 months ago

Note that the exponents are different, so it doesn't evaluate to 1.

Staff - 5 years, 10 months ago

16-1/16-1=1

- 5 years, 10 months ago

Note that the exponents are different, so it doesn't evaluate to 1.

Staff - 5 years, 10 months ago

Scratch that, it appears to check out.

- 5 years, 10 months ago

the answer is 16^50+16^25+1 16 leaves a remainder of 1 when divided by 3. Therefore any power of 16 leaves a remainder 1 when divided by 3. Therefore the expression is divisible by 3 and hence is not prime.

- 5 years, 10 months ago

Haha :) I guess I can prove it

- 5 years, 10 months ago

- 5 years, 10 months ago

2^1=2, 2^2=4 ,2^3=8, 2^4=16 2^5=32, therefore 2 will come again after every 4 times, now (16)^125=2^500,(dividing 500 by 4 means remainder will zero imply the unit digit of 2^500 will gives 6, now if we subtractions 1 from 6 we will get 5 and similar way id case of denominator we will get the unit digit 5 . now as the numerator is > denominator with unit digit 5 in both the cases . therefore numerator will divisible by denominator which imply the fraction will not be a prime number it will be a composite number . )

- 5 years, 10 months ago

1. 35÷15 is not an integer.
2. 75÷15 is an integer and is prime.

- 5 years, 10 months ago