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)

## Comments

Sort by:

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

In \(2^{n}-1\)

Just to make a start I took

*n *to be aneven 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\)

Log in to reply

– Alexander Xue · 3 years, 7 months ago

\(2^{n/2}+1\) can possibly be prime factorized into primes lower than 257.Log in to reply

However, there is the flaw that Abhishek's solution relies on the fact that \(n = 2^m\). – Bob Krueger · 3 years, 7 months ago

Log in to reply

To show that it is the minimum, you have to check all smaller values. This is slightly tedious. – Chung Kevin · 3 years, 7 months ago

Log in to reply

– Peng Ying Tan · 3 years, 7 months ago

Thanks for the solution!Log in to reply

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. – Alexander Xue · 3 years, 7 months ago

Log in to reply

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. – Peng Ying Tan · 3 years, 7 months agoLog in to reply

– Alexander Xue · 3 years, 7 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.Log in to reply

– Peng Ying Tan · 3 years, 7 months ago

Ok. Thanks Alexander!Log in to reply

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. – Bob Krueger · 3 years, 7 months ago

Log in to reply

517*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} \). – Alexander Xue · 3 years, 7 months ago

Log in to reply

– Mohammed Bezai · 3 years, 7 months ago

2^16 is congruent to 3 mod 13 !Log in to reply

– Alexander Xue · 3 years, 7 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.Log in to reply

– Peng Ying Tan · 3 years, 7 months ago

So the answer is 16?Log in to reply

– Bob Krueger · 3 years, 7 months ago

Shoot! That was silly of me. I'll change it.Log in to reply

– Bogdan Simeonov · 3 years, 7 months ago

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

– Bogdan Simeonov · 3 years, 7 months ago

oops...I was a little late saying this.Log in to reply

theorm – Shah Faisal · 3 years, 7 months ago

Log in to reply

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 – Srijon Sen · 3 years, 7 months ago

Log in to reply

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? – Sudeshna Pontula · 3 years, 7 months ago

Log in to reply

4 – Aditya Singh · 3 years, 7 months ago

Log in to reply

– Peng Ying Tan · 3 years, 7 months ago

4 is the answer? Can you explain why?Log in to reply

15=3×5

It is a product of two primes, not four...... – Peng Ying Tan · 3 years, 7 months ago

Log in to reply