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)

#NumberTheory #Primes #HelpMe!

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 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"

Math	Appears 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}$

Comments

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

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

Alexander Xue - 7 years, 5 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$ .

Bob Krueger - 7 years, 5 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.

Chung Kevin - 7 years, 5 months ago

Thanks for the solution!

A Former Brilliant Member - 7 years, 5 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.

Bob Krueger - 7 years, 5 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}$ .

Alexander Xue - 7 years, 5 months ago

2^16 is congruent to 3 mod 13 !

Mohammed Bezai - 7 years, 5 months ago

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

@Alexander Xue – So the answer is 16?

A Former Brilliant Member - 7 years, 5 months ago

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

Bogdan Simeonov - 7 years, 5 months ago

@Bogdan Simeonov – oops...I was a little late saying this.

Bogdan Simeonov - 7 years, 5 months ago

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

Bob Krueger - 7 years, 5 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.

Alexander Xue - 7 years, 5 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.

A Former Brilliant Member - 7 years, 5 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.

Alexander Xue - 7 years, 5 months ago

@Alexander Xue – Ok. Thanks Alexander!

A Former Brilliant Member - 7 years, 5 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?

Sudeshna Pontula - 7 years, 5 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

Srijon Sen - 7 years, 5 months ago

theorm

Shah Faisal - 7 years, 5 months ago

Aditya Singh - 7 years, 5 months ago

4 is the answer? Can you explain why?

A Former Brilliant Member - 7 years, 5 months ago

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

15=3×5

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

A Former Brilliant Member - 7 years, 5 months ago

Math	Appears 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}$