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

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

Log in to reply

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\).

Log in to reply

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.

Log in to reply

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.

Log in to reply

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.Log in to reply

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

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.

Log in to reply

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 (3

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} \).

Log in to reply

2^16 is congruent to 3 mod 13 !

Log in to reply

Log in to reply

Log in to reply

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

Log in to reply

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

Log in to reply

Log in to reply

theorm

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

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?

Log in to reply

4

Log in to reply

4 is the answer? Can you explain why?

Log in to reply

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

15=3×5

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

Log in to reply