Bulgarian Problem

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

#NumberTheory #Exams #MathProblem #Math

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

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

Then we have:

$p(2^{p-1}-1)=p^2x^2 \Rightarrow (2^{p-1}-1)=px^2$

Let $p=2$

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

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

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

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

$(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 $p$ divides one of the two factors, the other one must be a perfect square.

An odd perfect square is always $\equiv 1 \pmod{4}$ .

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

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

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

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

$2^{\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=3$ and $p=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.

Ciao.

Sebastiano R - 7 years, 8 months ago

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

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

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

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

Thus, unless $p$ is truly enormous Wieferich prime, the only possibilities are $p=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 - 7 years, 8 months ago

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

Now do the case of $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 - 7 years, 8 months ago

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

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

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

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

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

$(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 $(2^{\frac {p-1}{2}}-1)<(2^{\frac {p-1}{2}}+1)$ there are three possible cases:

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

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

Let $n^k=x^ky^k$ with $MCD(x,y)=1$

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

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

$[2b]$ : $k$ is odd: $(x^k+1)=(x+1)(x^{k-1}-x^{k-2}+...-x+1)=2^{\frac {p-1}{2}}$ . Since $p>3$ we have that $2^{\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) \equiv 0 \pmod{2}$ : the expression $(x^{k-1}-x^{k-2}+...-x+1)$ has an odd number of odd factors so it is odd $\rightarrow$ Absurd!

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

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

$[3b]$ : $k$ is odd: $(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 $(x-1) \equiv 0 \pmod{2}$ and the expression $(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=3$ and $p=7$ . I hope the proof works this time!

Ciao.

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

Sebastiano R - 7 years, 8 months ago

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

@Sebastiano R – There are more cases than this. The most general decomposition is $2^{\frac12(p-1)}-\varepsilon = p^{ak-1}u^k \qquad 2^{\frac12(p-1)}+\varepsilon = v^k$ where $\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 - 7 years, 8 months ago

@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

$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 - 7 years, 8 months ago

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

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

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

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

Hint: Greedy Calvinosaurus Dinosaur.

Calvin Lin Staff - 7 years, 8 months ago

The first statement is true for all $p>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 $p$ there is an integer $x$ such that $2^{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)$ are $(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 - 7 years, 8 months ago

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

Not a Wieferich prime in sight ...

The proof has been slightly amended to allow for the possibility that $x$ has $p$ as a repeated factor.

Suppose that $p$ is prime and $p(2^{p-1}-1) \,=\, x^k$ for some integer $x$ and some integer $k \ge 2$ . Certainly $p\ge 3$ is odd. Since their difference is $2$ and they are both odd, the numbers $2^{\frac12(p-1)} - 1$ and $2^{\frac12(p-1)}+1$ are coprime. By considering the various prime factors of $x$ , we deduce that we must be able to write $2^{\frac12(p-1)} - \varepsilon \; = \; p^{ak-1}u^k \qquad 2^{\frac12(p-1)} + \varepsilon \; = \; v^k$ for some $\varepsilon \in \{-1,1\}$ , some integer $a \ge 1$ and odd positive integers $u,v$ , where $u,v,p$ are pairwise coprime.

If $k$ is odd then $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-\varepsilon = 2^m$ for some $0 \le m \le \tfrac12(p-1)$ . Thus we deduce that $v^j\varepsilon^{k-1-j} \,\equiv\, \varepsilon^{k-1} = 1$ modulo $2^m$ for all $0 \le j \le k-1$ , and hence $A \; = \; \sum_{j=0}^{k-1} v^j \varepsilon^{k-1-j} \; \equiv \; k \qquad \qquad (2^m)$ If $m \ge 1$ , this implies that $A$ is odd. Since $A$ divides $2^{\frac12(p-1)}$ , this implies that $A=1$ , and hence $v^k-\varepsilon = v-\varepsilon$ . Since $k \ge 3$ we deduce that $v=1$ . Since $2^{\frac12(p-1)} + \varepsilon \,=\, v^k = 1$ , we deduce that $\varepsilon = -1$ and that $p=3$ . But then $3^{ak-1}u^k \,=\, 2$ , so that $a=k=1$ and $u=2$ . This does not work, so we must have $m=0$ , so that $v-\varepsilon = 1$ . Thus we deduce that $v=2$ , which cannot happen. This case is impossible.
If $k=2m$ is even and $\varepsilon = 1$ , then $2^{\frac12(p-1)} = v^{2m}-1 = (v^m-1)(v^m+1)$ , so that $v^m-1$ and $v^m+1$ are powers of $2$ which differ by $2$ . Thus $v^m-1=2$ and $v^m+1=4$ , so that $v=3$ and $m=1$ , so that $k=2$ . But then $2^{\frac12(p-1)} = 8$ , so that $p=7$ . This works with $a=u=1$ .
If $k=2m$ is even and $\varepsilon = -1$ then $v^k \equiv 1$ modulo $8$ , and $2^{\frac12(p-1)} = v^k + 1 \equiv 2$ modulo $8$ . Thus we deduce that $2^{\frac12(p-1)} = 2$ , and hence $p=3$ . In this case $k=2$ . Again we have $a=u=1$ .

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

Mark Hennings - 7 years, 8 months ago

the values of p can be 3 and 7

shreyansh chhajer - 7 years, 8 months ago

nice

Quanwei Lei - 7 years, 8 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}$