Bulgarian Problem

Find all prime numbers pp such as p(2p11) p(2^{p-1}-1) is a kth power of an integer and k2 k \geq 2 .

Note by Francesca Randone
6 years, 1 month ago

No vote yet
24 votes

  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}


Sort by:

Top Newest

ASSUMPTION* p2\rightarrow p^{2} doesn't divide (2p11)(2^{p-1}-1).

Then we have:

p(2p11)=p2x2(2p11)=px2p(2^{p-1}-1)=p^2x^2 \Rightarrow (2^{p-1}-1)=px^2

Let p=2p=2

(2211)=2x2x2=12(2^{2-1}-1)=2x^{2} \Rightarrow x^{2}=\frac {1}{2} \rightarrow Absurd!

Then p>2p>2 and MCD(2,p)=1MCD (2,p)=1. We are in the hypotesis of the Fermat's Little Theorem!

So (2p11)0(modp)(2^{p-1}-1) \equiv 0 \pmod{p}

pp is an odd prime number so (p1)(p-1) is even and we can decompose (2p11)(2^{p-1}-1) as a difference of squares:

(2p121)(2p12+1)=px2(2^{\frac {p-1}{2}}-1)(2^{\frac {p-1}{2}}+1)=px^{2}

The two factors of the LHS are two consecutive odd numbers so they are coprime. It follows that, if pp divides one of the two factors, the other one must be a perfect square.

An odd perfect square is always 1(mod4)\equiv 1 \pmod{4}.

(2p121)1(mod4)(2^{\frac {p-1}{2}}-1)\equiv 1 \pmod{4} only if 2p12=2p=32^{\frac {p-1}{2}}=2 \Rightarrow p=3 which is a solution.

From now on p>3p>3 and then: (2p121)3(mod4)(2^{\frac {p-1}{2}}-1)\equiv 3 \pmod{4} and (2p12+1)1(mod4)(2^{\frac {p-1}{2}}+1)\equiv 1 \pmod{4}

So it must be (2p12+1)=y22p12=(y1)(y+1)(2^{\frac {p-1}{2}}+1)=y^2 \Rightarrow 2^{\frac {p-1}{2}}=(y-1)(y+1)

(y1)(y-1) and (y+1)(y+1) must be power of 22 whose difference is 22 and the only possible case is 21=22^{1}=2 and 22=42^{2}=4 which we obtain for y=3y=3. Then we have:

2p12=(31)(3+1)=8p=72^{\frac {p-1}{2}}=(3-1)(3+1)=8 \Rightarrow p=7 which is the second solution.

This shows that there are only two solutions: p=3p=3 and p=7p=7.

It only remains to prove the ASSUMPTION* at the beginning but I have to think about it. If someone has some ideas please write them down.


Sebastiano R - 6 years, 1 month ago

Log in to reply

Prime numbers pp for which p2p^2 divides 2p112^{p-1}-1 are called Wieferich primes. There are only two small(ish) Wieferich primes: 10931093 and 35113511. The next biggest one, if it exists, is at least 101510^{15}, I read.

If pp is not a Wieferich prime, then k=2k=2, and your argument finishes things off.

If p=1093p=1093 then, since 109321093^2 divides 2109212^{1092}-1, but 109331093^3 does not, we must have k=3k=3. But 33 divides 2109212^{1092}-1, and 2727 does not, so this is not possible.

If p=3511p=3511 then, since 351123511^2 divides 2351012^{3510}-1, but 351133511^3 does not, we must have k=3k=3. But 31=25131=2^5-1 divides 2351012^{3510}-1, and 31331^3 does not, so this is not possible.

Thus, unless pp is truly enormous Wieferich prime, the only possibilities are p=3,7p=3,7. Perhaps it is possible to have a general argument like the specific ones I gave for the small Wieferich primes to cope with the case of any larger ones. I will need to think about that.

Mark Hennings - 6 years, 1 month ago

Log in to reply

Great approach. I prefer to think of it as that you done the case of k=2k=2 .

Now do the case of k3 k \geq 3 . As a hint, I used a nuclear bomb to solve the problem. I believe that less powerful weaponry will work though.

Edit: I found a method that uses elementary number theory.

Calvin Lin Staff - 6 years, 1 month ago

Log in to reply

This proof was made by Fabrizio B. I only helped him to formalize and write it down.

We have to find all primes pp such as p(2p11)=qkp(2^{p-1}-1)=q^k with pp prime and qq and kk positive integers (k>1)(k>1).

We can rewrite the expression as p(2p11)=pknk(2p11)=pk1nkp(2^{p-1}-1)=p^kn^k \Rightarrow (2^{p-1}-1)=p^{k-1}n^k.

Let p=2(2211)=2k1nk=1p=2 \rightarrow (2^{2-1}-1)=2^{k-1}n^{k}=1 but k>1k>1 \rightarrow Absurd!

Then p>2p>2: pp is an odd prime number so (p1)(p-1) is even and we can decompose (2p11)(2^{p-1}-1) as a difference of squares:

(2p121)(2p12+1)=pk1nk(2^{\frac {p-1}{2}}-1)(2^{\frac {p-1}{2}}+1)=p^{k-1}n^{k}

The two factors of the LHS are two consecutive odd numbers so they are coprime and taking into account that (2p121)<(2p12+1)(2^{\frac {p-1}{2}}-1)<(2^{\frac {p-1}{2}}+1) there are three possible cases:

[1][1]: (2p121)=1(2^{\frac {p-1}{2}}-1)=1 and (2p12+1)=pk1nk(2^{\frac {p-1}{2}}+1)=p^{k-1}n^{k}.

From the first equation we obtain p=3p=3 which is the first solution. From now on, p>3p>3

Let nk=xkykn^k=x^ky^k with MCD(x,y)=1MCD(x,y)=1

[2][2]: (2p121)=xk(2^{\frac {p-1}{2}}-1)=x^k and (2p12+1)=ykpk1(2^{\frac {p-1}{2}}+1)=y^kp^{k-1}

[2a][2a]: kk is even: xkx^k is a perfect square then it is 1(mod4)\equiv 1 \pmod{4}, but (2p121)3(mod4)(2^{\frac {p-1}{2}}-1) \equiv 3 \pmod{4} for p>3p>3 \rightarrow Absurd!

[2b][2b]: kk is odd: (xk+1)=(x+1)(xk1xk2+...x+1)=2p12(x^k+1)=(x+1)(x^{k-1}-x^{k-2}+...-x+1)=2^{\frac {p-1}{2}}. Since p>3p>3 we have that 2p12>22^{\frac {p-1}{2}}>2 so the RHS is even and doesn't have odd factors in his factorization. Then the factors of LHS must both be even. Then (x+1)0(mod2)(x+1) \equiv 0 \pmod{2}: the expression (xk1xk2+...x+1)(x^{k-1}-x^{k-2}+...-x+1) has an odd number of odd factors so it is odd \rightarrow Absurd!

[3][3]: (2p121)=ykpk1(2^{\frac {p-1}{2}}-1)=y^kp^{k-1} and (2p12+1)=xk(2^{\frac {p-1}{2}}+1)=x^k

[3a][3a]: kk is even: from the second equation (xk/21)(xk/2+1)=2p12(xk/21)(x^{k/2}-1)(x^{k/2}+1)=2^{\frac {p-1}{2}} \rightarrow (x^{k/2}-1) and (xk/2+1)(x^{k/2}+1) must be powers of 2 whose difference is 2 and the only possible case is 22 and 44 which we obtain from x=3x=3 and k=2k=2. Then 2p12=8p=72^{\frac {p-1}{2}}=8 \rightarrow p=7 which is the second solution.

[3b][3b]: kk is odd: (xk1)=(x1)(xk1+xk2+...+x+1)=2p12(x^k-1)=(x-1)(x^{k-1}+x^{k-2}+...+x+1)=2^{\frac {p-1}{2}}. Then (as in 2b) it must be (x1)0(mod2)(x-1) \equiv 0 \pmod{2} and the expression (xk1+xk2+...+x+1)(x^{k-1}+x^{k-2}+...+x+1) has an odd number of odd factors so it is odd \rightarrow Absurd!

This shows that the only solutions are p=3p=3 and p=7p=7. I hope the proof works this time!


EDITED 2b: Calvin, could you please tell me the other steps which don't work? thanks

Sebastiano R - 6 years ago

Log in to reply

@Sebastiano R This is a good start, and I would encourage you to review this proof for clarity and content. There are slight gaps still, like that pointed out by Mark, and another in case 2b, as you have to show that the factor is not 1, which is a power of 2.

You can do better to highlight the important steps of your argument, and choosing the way to present the cases. E.g. given the slight hiccup of 2b, it is better to present case 3 before case 2.

Calvin Lin Staff - 6 years ago

Log in to reply

@Sebastiano R There are more cases than this. The most general decomposition is 212(p1)ε=pak1uk212(p1)+ε=vk 2^{\frac12(p-1)}-\varepsilon = p^{ak-1}u^k \qquad 2^{\frac12(p-1)}+\varepsilon = v^k where ε=±1\varepsilon = \pm1. While it is possible to reduce these more general options to your three, at the time you introduce these as the possible cases, the fact that a more general decomposition is not possible is not yet obvious.

Mark Hennings - 6 years ago

Log in to reply

@Mark Hennings While I agree that you gave the general decomposition form, observe that the important contradiction that was achieved was in showing that there is no solutions to

212(p1)+ϵ=vk. 2^{ \frac{1}{2} (p-1) } + \epsilon = v^k.

This is true by Mihailescu's theorem on consecutive perfect powers, which was the nuclear bomb that I referred to. There exists a more elementary method, which was the parity argument that was laid out.

Calvin Lin Staff - 6 years ago

Log in to reply

@Calvin Lin Mihailescu's theorem, or his proof of a much older conjecture, is a mere 11 years old. As someone who has never been a Number Theorist, I cannot hope to keep track of every research development that recent (nobody can without the benefit of a university paying for access to the journals). There is nothing wrong with finding the "more elementary method" here!

I regret that you have not commented on my posted solution of this problem, which predates Sebastiano's.

Mark Hennings - 6 years ago

Log in to reply

@Mark Hennings I regret that I have limited resources to work with, and hence cannot write a verbal response to every single solution or discussion that is presented. In fact, more often that not, the fact that I didn't respond indicates that your statements are (mostly) right. I chose to respond to Sebastiano, as that allowed me to point out parts of his proof that could be cleaned up / presented better.

I think that you misinterpreted what I meant. I am (almost always) in favor of finding the elementary method, especially given that this was a Bulgarian olympiad problem. This is why in my previous comment, I stated that I only had a nuclear bomb and then edited it later to say that I found an elementary approach. I personally have not reviewed Mihailescu's theorem, so I do not know the depth of understanding required.

Calvin Lin Staff - 6 years ago

Log in to reply

Judging from the indicated interest but lack of comments, I'd drop some hints.

Hint: Is it possible that p2p11 p \mid 2^{p-1} -1 ? Is it possible that p2(2p11) p^2 \mid (2^{p-1} -1 ) ?

Hint: Greedy Calvinosaurus Dinosaur.

Calvin Lin Staff - 6 years, 1 month ago

Log in to reply

The first statement is true for all p>2p>2 by Fermat's Little Theorem. The second statement seems to never be true, and I can't seem to be able to figure out why. If it is, in fact, never true, it clearly shows that k = 2. Then it remains to find for which promes pp there is an integer xx such that 2p11=px22^{p-1}-1 = p \cdot x^2. These primes are the ones sought in the problem. My conjecture is that the only pairs (p,x)(p,x) are (3,1),(7,3)(3,1),(7,3), but again, I have no proof of this. Hopefully this comment gives someone a push to make a better one with some actual math.

Sotiri Komissopoulos - 6 years, 1 month ago

Log in to reply

Good work. Sometimes my hints are cryptic. The second statement actually is possible (Gasp!) , so it's good that you can't figure out a proof. See Mark's comment below.

Wieferich primes are one of my favorite counter examples of using small cases. That is why my first hint was written as such.

Calvin Lin Staff - 6 years, 1 month ago

Log in to reply

Not a Wieferich prime in sight ...

The proof has been slightly amended to allow for the possibility that xx has pp as a repeated factor.

Suppose that pp is prime and p(2p11)=xkp(2^{p-1}-1) \,=\, x^k for some integer xx and some integer k2k \ge 2. Certainly p3p\ge 3 is odd. Since their difference is 22 and they are both odd, the numbers 212(p1)12^{\frac12(p-1)} - 1 and 212(p1)+12^{\frac12(p-1)}+1 are coprime. By considering the various prime factors of xx, we deduce that we must be able to write 212(p1)ε  =  pak1uk212(p1)+ε  =  vk 2^{\frac12(p-1)} - \varepsilon \; = \; p^{ak-1}u^k \qquad 2^{\frac12(p-1)} + \varepsilon \; = \; v^k for some ε{1,1}\varepsilon \in \{-1,1\}, some integer a1a \ge 1 and odd positive integers u,vu,v, where u,v,pu,v,p are pairwise coprime.

  • If kk is odd then 212(p1)  =  vkε  =  vkεk  =  (vε)j=0k1vjεk1j  =  (vε)A 2^{\frac12(p-1)} \; = \; v^k - \varepsilon \; = \; v^k - \varepsilon^k \; = \; (v - \varepsilon)\sum_{j=0}^{k-1}v^j\varepsilon^{k-1-j} \; = \; (v-\varepsilon)A Thus vε=2mv-\varepsilon = 2^m for some 0m12(p1)0 \le m \le \tfrac12(p-1). Thus we deduce that vjεk1jεk1=1v^j\varepsilon^{k-1-j} \,\equiv\, \varepsilon^{k-1} = 1 modulo 2m2^m for all 0jk10 \le j \le k-1, and hence A  =  j=0k1vjεk1j    k(2m) A \; = \; \sum_{j=0}^{k-1} v^j \varepsilon^{k-1-j} \; \equiv \; k \qquad \qquad (2^m) If m1m \ge 1, this implies that AA is odd. Since AA divides 212(p1)2^{\frac12(p-1)}, this implies that A=1A=1, and hence vkε=vεv^k-\varepsilon = v-\varepsilon. Since k3k \ge 3 we deduce that v=1v=1. Since 212(p1)+ε=vk=12^{\frac12(p-1)} + \varepsilon \,=\, v^k = 1, we deduce that ε=1\varepsilon = -1 and that p=3p=3. But then 3ak1uk=23^{ak-1}u^k \,=\, 2, so that a=k=1a=k=1 and u=2u=2. This does not work, so we must have m=0m=0, so that vε=1v-\varepsilon = 1. Thus we deduce that v=2v=2, which cannot happen. This case is impossible.

  • If k=2mk=2m is even and ε=1\varepsilon = 1, then 212(p1)=v2m1=(vm1)(vm+1)2^{\frac12(p-1)} = v^{2m}-1 = (v^m-1)(v^m+1), so that vm1v^m-1 and vm+1v^m+1 are powers of 22 which differ by 22. Thus vm1=2v^m-1=2 and vm+1=4v^m+1=4, so that v=3v=3 and m=1m=1, so that k=2k=2. But then 212(p1)=82^{\frac12(p-1)} = 8, so that p=7p=7. This works with a=u=1a=u=1.

  • If k=2mk=2m is even and ε=1\varepsilon = -1 then vk1v^k \equiv 1 modulo 88, and 212(p1)=vk+122^{\frac12(p-1)} = v^k + 1 \equiv 2 modulo 88. Thus we deduce that 212(p1)=22^{\frac12(p-1)} = 2, and hence p=3p=3. In this case k=2k=2. Again we have a=u=1a=u=1.

Thus the only possible solutions are with k=2k=2, and they are p=3,7p=3,7.

Mark Hennings - 6 years ago

Log in to reply

the values of p can be 3 and 7

shreyansh chhajer - 6 years, 1 month ago

Log in to reply


Quanwei Lei - 6 years ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...