×

# 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
2 years, 5 months ago

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. · 2 years, 5 months ago

"Sacrosanct" is such a beautiful word. Well done, too. · 2 years, 4 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$$. · 2 years, 5 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)$$ . · 2 years, 5 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. · 2 years, 5 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... · 2 years, 5 months ago

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

$\begin{eqnarray} && \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{eqnarray}$

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. · 2 years, 5 months ago

Oh ooops. Typo. Fixed!

The question has to be much more interesting than that ... Staff · 2 years, 5 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}$$ · 2 years, 5 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 :) · 2 years, 5 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. · 2 years, 5 months ago

OH MY GOODNESS THAT SAYS 16. IGNORE THE PREVIOUS COMMENT. · 2 years, 5 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{eqnarray} 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{eqnarray}$

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. · 2 years, 5 months ago

You wrote : x^2 + 2 x + 1 instead of x^2 + x + 1 at the 4th line · 2 years, 5 months ago

$$x^4 + x^3 + x^2 + x + 1 = (x^2 + x+ 1)^2 - x(x^2 + 2x + 1)$$ is correct. · 2 years, 5 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. · 2 years, 5 months ago

Scratch that, it appears to check out. · 2 years, 5 months ago

16-1/16-1=1 · 2 years, 5 months ago

Note that the exponents are different, so it doesn't evaluate to 1. Staff · 2 years, 5 months ago

1 · 2 years, 5 months ago

Note that the exponents are different, so it doesn't evaluate to 1. Staff · 2 years, 5 months ago

answer is 1,048,576 · 2 years, 5 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 . ) · 2 years, 5 months ago

1. 35÷15 is not an integer.
2. 75÷15 is an integer and is prime.
· 2 years, 5 months ago