Waste less time on Facebook — follow Brilliant.
×

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 Peng Ying Tan
3 years, 1 month ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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

Abhishek Abhi · 3 years, 1 month ago

Log in to reply

@Abhishek Abhi \(2^{n/2}+1\) can possibly be prime factorized into primes lower than 257. Alexander Xue · 3 years, 1 month ago

Log in to reply

@Alexander Xue 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\). Bob Krueger · 3 years, 1 month ago

Log in to reply

@Abhishek Abhi 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. Chung Kevin · 3 years, 1 month ago

Log in to reply

@Abhishek Abhi Thanks for the solution! Peng Ying Tan · 3 years, 1 month ago

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, 1 month ago

Log in to reply

@Alexander Xue 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. Peng Ying Tan · 3 years, 1 month ago

Log in to reply

@Peng Ying Tan 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. Alexander Xue · 3 years, 1 month ago

Log in to reply

@Alexander Xue Ok. Thanks Alexander! Peng Ying Tan · 3 years, 1 month ago

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, 1 month ago

Log in to reply

@Bob Krueger 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} \). Alexander Xue · 3 years, 1 month ago

Log in to reply

@Alexander Xue 2^16 is congruent to 3 mod 13 ! Mohammed Bezai · 3 years, 1 month ago

Log in to reply

@Mohammed Bezai 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. Alexander Xue · 3 years, 1 month ago

Log in to reply

@Alexander Xue So the answer is 16? Peng Ying Tan · 3 years, 1 month ago

Log in to reply

@Alexander Xue Shoot! That was silly of me. I'll change it. Bob Krueger · 3 years, 1 month ago

Log in to reply

@Alexander Xue Actually, using Fermat 2^16 is congruent to 2^4, not 2^3 (mod 13) Bogdan Simeonov · 3 years, 1 month ago

Log in to reply

@Bogdan Simeonov oops...I was a little late saying this. Bogdan Simeonov · 3 years, 1 month ago

Log in to reply

theorm Shah Faisal · 3 years 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 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 ago

Log in to reply

4 Aditya Singh · 3 years, 1 month ago

Log in to reply

@Aditya Singh 4 is the answer? Can you explain why? Peng Ying Tan · 3 years, 1 month ago

Log in to reply

@Peng Ying Tan If n=4, 2^4-1=16-1=15.

15=3×5

It is a product of two primes, not four...... Peng Ying Tan · 3 years, 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...