# Product of four prime numbers

Hi fellow brilliantians, may I know the method to solve the following problem(from a maths competition)?

Problem:Find the smallest value of $$n$$ such that $$2^n-1$$ is the product of four prime numbers.

Is the answer $$16$$?

This question maybe be very simple for you, but I would like to know the solution and how do you solved it. Can you post it below as a comment?

Thanks fellow Brilliantians!(This is my first note(discussion)! :-D)

Note by Brilliant Member
4 years, 10 months ago

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:

Even if we don't know the value of n it can simply be done using backtracking......

In $$2^{n}-1$$

1. Just to make a start I took *n * to be an even no.

now, $$2^{n}-1$$ can be broken into $$(2^{n/2}-1)(2^{n/2}+1)$$

and which can be further broken as $$(2^{n/4}-1)(2^{n/4}+1)(2^{n/2}+1)$$

and so goes on until every subtraction term is broken .....and it comes down to

$$(2^{1}-1)(2^{1}+1)(2^{2}+1)(2^{4}+1)(2^{8}+1).............(2^{n/2}+1)$$ which is

$$1*3*5*17*257.......(2^{n/2}+1)$$

As we already got our four prime factors we will limit $$n/2$$ above to $$8$$ which gives $$n=16$$

- 4 years, 10 months ago

$$2^{n/2}+1$$ can possibly be prime factorized into primes lower than 257.

- 4 years, 10 months ago

It may be, but we would already have the primes listed if we factorized that further. So the case he makes is the least possible for four prime factors.

However, there is the flaw that Abhishek's solution relies on the fact that $$n = 2^m$$.

- 4 years, 10 months ago

You have only shown that 16 is a possible solution. You need to show that it is the minimum.

To show that it is the minimum, you have to check all smaller values. This is slightly tedious.

- 4 years, 10 months ago

Thanks for the solution!

- 4 years, 10 months ago

We note that if n makes the expression divisible by a prime p, then xn makes the expression divisible by p as well, for x is a non-negative integer (consider order if this confuses you [if you don't know what order is you might want to look it up]). So what are the least integers that have 4 factors (excluding 1 because 2^1-1 doesn't count as a prime factor)? If you've found 16, we'd check up to that. The only ones are 12 and 16. 12 does work: it's 5 factors excluding 1 are 2, 3, 4, 6, and 12. Checking the primes involved in these numbers, we find that 6 offers no new prime factor (only the prime factors 3 and 7, already used by 2 and 3). However, 2, 3, 4, and 12 offer distinct prime factors. The factor 12 works because by Fermat's Little Theorem, $$2^{12}-1$$ is divisible by 13. Thus 12 is the answer. To get the answer from the start without knowing/suspecting 16, I would start by finding n for distinct prime factors. Then I'd notice that hmm, 2, 3 can make for a low >4 factor number. Then I'd check 12, and it would work. Edit: This solution has mistakes in it. 12 actually doesn't work because 3 divides it twice. So the next number to check is 16, and that works.

- 4 years, 10 months ago

Can you explain clearer? I cannot get it from "12 does work:it's 5 factors excluding 1 are 2,3,4,6 & 12...Thus 12 is the answer.". May I know why the "5 factors" are related to $$2^{12}-1$$? And why 12 is the answer?

I check it:

$$2^{12}-1=4095=3^2\times7\times13\times5$$

But 3^2 is not a prime...

I think the problem wants the equation equals to product of four primes, means $$p_1\times p_2\times p_3\times p_4$$, while the $$p$$'s are primes.

- 4 years, 10 months ago

Woops. I had thought it said that it had 4 prime factors, my bad. To clarify: in just being divisible by 4 prime factors, 12 works because, for example, $$2^2 \equiv 1 \pmod 3$$. Taking this to the 6th power obtains $$2^{12} \equiv 1 \pmod 3$$, which implies $$2^{12}-1 \equiv 0 \pmod 3$$. This works similarly for the other factors, which was what I was referring to in my solution. Since $$2^2$$, $$2^3$$, $$2^4$$, and $$2^{12}$$ were congruent to 1 in different prime modulos, then 4 primes divided $$2^{12}-1$$. I misread though. So since 12 doesn't work because of the two 3's and 16 works, then $$\boxed{16}$$ is the answer.

- 4 years, 10 months ago

Ok. Thanks Alexander!

- 4 years, 10 months ago

For this type of question, you may consider 1 a power of any magnitude. By this I mean that if $$n=16$$, then you factor that expression as the difference of two squares, and then factor one of the resulting factors, and so on. Using $$n=16$$, we can factor: $$2^{16}-1 = (2^8+1)(2^8-1) = (2^8+1)(2^4+1)(2^4-1) = (2^8+1)(2^4+1)(2^2+1)(2^2-1) =$$ $$(2^8+1)(2^4+1)(2^2+1)(2^1+1)(2^1-1) = 257 \cdot 17 \cdot 5 \cdot 3 \cdot 1$$ Now, it does matter if the primes must be distinct. If they must be distinct, this could be a possible answer. If they don't have to be distinct, I would bet that this probably isn't the answer. But all of this doesn't help you answer the question.

First, if you haven't heard of them, $$2^n-1$$ is the form of a Mersenne Number. The way I would tackle this problem is using this knowledge of Mersenne primes and these factoring techniques. I would start with $$n=1$$ and continue on up. Let me do that and I'll get back to you. Thanks for posting on Brilliant.

- 4 years, 10 months ago

Hmm something is wrong here, because by Fermat's, $$2^{16} \equiv 2^3 \equiv 8 \pmod {13}$$, so the expression is congruent to 7 mod 13. The mistake here is that $$2^8+1$$ can't be expressed as a sum of cubes. But the expression is divisible by 4 distinct primes (3517*257 from your equation before the sum of cubes was applied) , so 16 works.

Edit: It should be $$2^4$$ not $$2^3$$. $$2^{16} \equiv 2^4 \equiv 3 \pmod {13}$$.

- 4 years, 10 months ago

2^16 is congruent to 3 mod 13 !

- 4 years, 10 months ago

Yeah woops it should be $$2^4$$ instead of $$2^3$$. Was thinking about one version of Fermat's and the other version at the same time.

- 4 years, 10 months ago

- 4 years, 10 months ago

Shoot! That was silly of me. I'll change it.

- 4 years, 10 months ago

Actually, using Fermat 2^16 is congruent to 2^4, not 2^3 (mod 13)

- 4 years, 10 months ago

oops...I was a little late saying this.

- 4 years, 10 months ago

theorm

- 4 years, 9 months ago

2^2-1= 3 2^2+1=5 multiply and we get 2^4-1 (2^4-1)*(2^4+1)=(2^8-1) (2^8-1)(2^8+1)=(2^16-1).. so answer is 16.. since 2^n-1 is odd.. hence we cannot take 2 as the prime factorization

- 4 years, 10 months ago

Do the prime numbers that are factors of $$2^{n}-1$$ have to be distinct? Or just have 4 primes in its factorization, like 36?

- 4 years, 10 months ago

4

- 4 years, 10 months ago

4 is the answer? Can you explain why?

- 4 years, 10 months ago

If n=4, 2^4-1=16-1=15.

15=3×5

It is a product of two primes, not four......

- 4 years, 10 months ago