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 nn such that 2n12^n-1 is the product of four prime numbers.

Is the answer 1616?

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 A Former Brilliant Member
5 years, 10 months ago

No vote yet
1 vote

  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.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 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"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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

In 2n12^{n}-1

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

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

    and which can be further broken as (2n/41)(2n/4+1)(2n/2+1)(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

    (211)(21+1)(22+1)(24+1)(28+1).............(2n/2+1)(2^{1}-1)(2^{1}+1)(2^{2}+1)(2^{4}+1)(2^{8}+1).............(2^{n/2}+1) which is

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

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

Abhishek Abhi - 5 years, 10 months ago

Log in to reply

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

Alexander Xue - 5 years, 10 months ago

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=2mn = 2^m.

Bob Krueger - 5 years, 10 months ago

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.

Chung Kevin - 5 years, 10 months ago

Log in to reply

Thanks for the solution!

A Former Brilliant Member - 5 years, 10 months 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=16n=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=16n=16, we can factor: 2161=(28+1)(281)=(28+1)(24+1)(241)=(28+1)(24+1)(22+1)(221)=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) = (28+1)(24+1)(22+1)(21+1)(211)=25717531(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, 2n12^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=1n=1 and continue on up. Let me do that and I'll get back to you. Thanks for posting on Brilliant.

Bob Krueger - 5 years, 10 months ago

Log in to reply

Hmm something is wrong here, because by Fermat's, 216238(mod13)2^{16} \equiv 2^3 \equiv 8 \pmod {13}, so the expression is congruent to 7 mod 13. The mistake here is that 28+12^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 242^4 not 232^3. 216243(mod13)2^{16} \equiv 2^4 \equiv 3 \pmod {13} .

Alexander Xue - 5 years, 10 months ago

Log in to reply

2^16 is congruent to 3 mod 13 !

Mohammed Bezai - 5 years, 10 months ago

Log in to reply

@Mohammed Bezai Yeah woops it should be 242^4 instead of 232^3. Was thinking about one version of Fermat's and the other version at the same time.

Alexander Xue - 5 years, 10 months ago

Log in to reply

@Alexander Xue So the answer is 16?

A Former Brilliant Member - 5 years, 10 months ago

Log in to reply

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

Bogdan Simeonov - 5 years, 10 months ago

Log in to reply

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

Bogdan Simeonov - 5 years, 10 months ago

Log in to reply

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

Bob Krueger - 5 years, 10 months 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, 21212^{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 - 5 years, 10 months ago

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 21212^{12}-1? And why 12 is the answer?

I check it:

2121=4095=32×7×13×52^{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 p1×p2×p3×p4p_1\times p_2\times p_3\times p_4, while the pp's are primes.

A Former Brilliant Member - 5 years, 10 months ago

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, 221(mod3)2^2 \equiv 1 \pmod 3. Taking this to the 6th power obtains 2121(mod3)2^{12} \equiv 1 \pmod 3, which implies 21210(mod3)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 222^2, 232^3, 242^4, and 2122^{12} were congruent to 1 in different prime modulos, then 4 primes divided 21212^{12}-1. I misread though. So since 12 doesn't work because of the two 3's and 16 works, then 16\boxed{16} is the answer.

Alexander Xue - 5 years, 10 months ago

Log in to reply

@Alexander Xue Ok. Thanks Alexander!

A Former Brilliant Member - 5 years, 10 months ago

Log in to reply

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

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

Log in to reply

theorm

Shah Faisal - 5 years, 9 months ago

Log in to reply

4

Aditya Singh - 5 years, 10 months ago

Log in to reply

4 is the answer? Can you explain why?

A Former Brilliant Member - 5 years, 10 months ago

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

A Former Brilliant Member - 5 years, 10 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...