Balkan Mathematical Olympiad 2018 P4

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Balkan Mathematical Olympiad 2018 P4

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: BMO 2018

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

microsoft_office_word

66 posts

microsoft_office_word

#1 h May 9, 2018, 1:29 PM • 9 Y

Y by Mathuzb, samrocksnature, son7, megarnie, tiendung2006, Adventure10, Mango247, GeoKing, pomodor_ap

Find all primes $p$ and $q$ such that $3p^{q-1}+1$ divides $11^p+17^p$

Proposed by Stanislav Dimitrov,Bulgaria

This post has been edited 2 times. Last edited by microsoft_office_word, May 9, 2018, 2:29 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

98 posts

#4 h May 9, 2018, 2:09 PM • 8 Y

Y by TwoTimes3TimesSeven, Mathuzb, samrocksnature, microsoft_office_word, son7, megarnie, Adventure10, Mango247

The problem was proposed by Stanislav Dimitrov from Bulgaria

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

392 posts

Hamel

#5 h May 9, 2018, 2:09 PM • 3 Y

Y by samrocksnature, Adventure10, Mango247

Is it plus or minus?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

475 posts

Anar24

#6 h May 9, 2018, 2:10 PM • 3 Y

Y by samrocksnature, Adventure10, Mango247

The problem is quite similar to APMO 2012 and Turkey EGMO TST 2016.Just looking at order and quite difficult caseworks

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

475 posts

Anar24

#7 h May 9, 2018, 2:11 PM • 3 Y

Y by samrocksnature, Adventure10, Mango247

sorry forgot the statement.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

392 posts

Hamel

#8 h May 9, 2018, 2:12 PM • 3 Y

Y by samrocksnature, Adventure10, Mango247

I think it is plus. Method?

This post has been edited 3 times. Last edited by Hamel, May 9, 2018, 2:15 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

868 posts

#9 h May 9, 2018, 2:49 PM • 8 Y

Y by Hamel, Illuzion, Mathuzb, MathbugAOPS, Wizard_32, samrocksnature, Iora, Adventure10

Just take $3p^{q-1}+1=4^k 7^m t$ . where $(t,14)=1$
and note that $t\equiv 1 \pmod p$ .
And it is easy to show that $k\le 2$ and that $m\le 1$
then take both sides $\pmod p$ and finish small cases

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

211 posts

#10 h May 9, 2018, 3:22 PM • 3 Y

Y by samrocksnature, Adventure10, Mango247

why $m \leq 1$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

392 posts

Hamel

#11 h May 9, 2018, 3:24 PM • 4 Y

Y by Illuzion, samrocksnature, Adventure10, Mango247

$LTE$ yields that

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

431 posts

#12 h May 9, 2018, 3:56 PM • 3 Y

Y by samrocksnature, Adventure10, Mango247

rightways wrote:

Just take $3p^{q-1}+1=4^k 7^m t$ . where $(t,14)=1$
and note that $t\equiv 1 \pmod p$ .
And it is easy to show that $k\le 2$ and that $m\le 1$
then take both sides $\pmod p$ and finish small cases

Nice rightways, thanks

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

409 posts

#13 h May 9, 2018, 4:50 PM • 8 Y

Y by Illuzion, GGPiku, MihneaD, samrocksnature, Kugelmonster, Adventure10, Mango247, Gaunter_O_Dim_of_math

Indeed, $(p,q)=(3,3)$ is the only solution. If $p=2$ one can easily check that there are no solutions so suppose $p\ge 3$ .

Suppose that $q$ is odd; this gives $v_2(3p^{q-1}+1)=2$ . Take $r$ an odd prime dividing $3p^{q-1}+1$ . Then $r$ divides $11^p+17^p$ . As $11$ and $17$ are coprime, we get that $r$ divides $a^p+1$ , where $a=11\cdot 17^{-1} (\mathrm{mod}\ r)$ . Thus, $r$ divides $a^{2p}-1$ so the order of $a$ mod $r$ has to divide $2p$ . If the order is $1$ or $p$ ), then $r$ divides both $a^p-1$ and $a^p+1$ , so $r$ divides $2$ , a contradiction. If the order is $2$ , as $r$ divides $a^p+1$ , we get that $r$ divides $a+1$ so $r$ divides $28$ and hence $r=7$ . Otherwise the order is $2p$ so $2p$ divides $r-1$ . Thus, if $3p^{q-1}+1=7^t4r_1^{a_1}....r_k^{a_k}$ for some odd distinct primes $r_i$ and some nonnegative integer $t\ge 0$ (which by LTE is less or equal to $2$ ), by the previous we have $r_i\equiv 1 (\mathrm{mod}\ p)$ so $3p^{q-1}+1\equiv 4,28, 196(\mathrm{mod}\ p)$ and thereby we get $p\in \{3,5,13\}$ . A quick check gives $q=3$ the only possibility.

If $q=2$ , we have $3p+1$ divides $11^p+17^p$ . If $3p+1$ is not a power of two, proceeding as in the previous case we get that any odd prime divisor of $3p+1$ must be congruent with $1$ mod $2p$ . As $3p+1$ is even, we get that $3p+1\ge 2(2p-1)$ which gives again $p=3$ so $q=3$ , a contradiction. Thus $3p+1=2^k$ for some positive integer $k$ . Clearly $k$ has to be even, $k=2\ell$ so $3p=(2^{\ell}-1)(2^{\ell}+1)$ . As $(2^{\ell}-1,2^{\ell}+1)=1$ and $2^{\ell}-1<2^{\ell}+1$ we get that either $2^{\ell}-1=1,\ 2^{\ell}+1=3p$ or $2^{\ell}-1=3,\ 2^{\ell}+1=p$ . We therefore infer that either $p=3$ (in which case again $q=3$ but we supposed $q=2$ ) or $p=5$ . However, $p=5$ and $q=2$ would give $16$ dividing $11^5+17^5$ , a contradiction.

This post has been edited 1 time. Last edited by Aiscrim, May 9, 2018, 7:32 PM
Reason: I should not attempt Olympiad problems after so long. This solution is still incomplete, but I have lost my patience. One still needs to check a little more cases in the case when q=2 because 7 can also pop up in 3p+1.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

23 posts

#14 h May 9, 2018, 6:16 PM • 4 Y

Y by GGPiku, samrocksnature, Adventure10, Mango247

Let $r$ be an odd prime dividing $3p^{q-1}+1$ , so consequently $r$ divides $11^p+17^p$ . ( if $p$ is odd we have that $3p^{q-1}+1 \equiv 4 \pmod 8$ , and since this number is clearly bigger than $4$ , we know that it must have an odd prime divisor, and if $p$ is $2$ , our number is odd, and so our hypothesis is obvious)
If $p$ is $2$ we verify by hand.
We have that $11^p \equiv -17^p \pmod r$ , so $(\frac {11}{17})^{2p} \equiv 1 \pmod r$ . Let the order of $(\frac {11}{17})$ be $x$ . Thus, $x$ divides both $r-1$ and $2p$ and, since it can't be odd, it has to be either $2$ or $2p$ . If it is $2$ , we then have that $r$ divides $168$ and, since $r$ is odd and not $3$ , it has to be $7$ . If $x$ is $2p$ , we have that $r \equiv 1 \pmod {2p}$ . Taking these into consideration, we get that $3p^{q-1}+1=4^m7^ny$ , where $(y,14)=1$ and $y\equiv 1 \pmod p$ . By LTE, we have that $n$ is $2$ if $p=7$ (we verify by hand), or $n\le 1$ . Also, $m=1$ .
Taking $\pmod p$ , we get that $1 \equiv 4,28 \pmod p$ , so $0 \equiv 3, 27 \pmod p$ . Thus, $p=3$ and, after some casework, $q=3$ . Thus, the only solution is $(3,3)$ .
Edit:
Oops, forgot about $q=2$ . If there exists a prime $r$ that divides $3p+1$ and $r$ is not $7$ , we proceed as previously. if $3p+1$ is a power of $2$ , then it's exponent has to be even.
Thus, $3p=(2^x-1)(2^x+1)$ , and so $x$ is $1$ or $2$ , which means that $p$ is either $3$ or $5$ . We get a contradiction for both cases.
If $7$ divides $3p+1$ , then $3p+1=2^k7$ . $11^p$ is either $3$ or $1$ $\pmod 8$ , and $17^p$ is $1$ $\pmod p$ . Thus, $k\le 2$ , and we verify the cases by hand.

This post has been edited 3 times. Last edited by atmargi, May 9, 2018, 6:48 PM
Reason: i'm stoopid

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

558 posts

#15 h Oct 5, 2019, 7:47 PM • 2 Y

Y by samrocksnature, Adventure10

Illuzion wrote:

why $m \leq 1$ ?

Hamel wrote:

$LTE$ yields that

Can someone please elaborate this ?? I am new to LTE ....
I mean how do we bound $\nu _{(7)} 3p^{q-1}+ 1$

This post has been edited 4 times. Last edited by Aryan-23, Oct 5, 2019, 7:51 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

158 posts

#16 h Nov 12, 2019, 1:04 PM • 2 Y

Y by samrocksnature, Adventure10

Aryan-23 wrote:

Illuzion wrote:

why $m \leq 1$ ?

Hamel wrote:

$LTE$ yields that

Can someone please elaborate this ?? I am new to LTE ....
I mean how do we bound $\nu _{(7)} 3p^{q-1}+ 1$

you dont!
you use LTE to show V7 of the right hand side is 1.
so the left hand side can not be devisible by 49.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

558 posts

#17 h Nov 12, 2019, 2:08 PM • 3 Y

Y by samrocksnature, Adventure10, Mango247

Oh yeah , stupid me , thanks

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6877 posts

#18 h Aug 28, 2020, 1:31 AM • 8 Y

Y by Mathematicsislovely, v4913, samrocksnature, amano_hina, tiendung2006, Mathlover_1, Sedro, endless_abyss

Solution from OTIS office hours:

The answer is $(3,3)$ only which works. We first dispense of several edge cases:

One can check $p=2$ has no solutions.
One can check $p=3$ has only the solution $(3,3)$ .

Claim: Every prime dividing $11^p+17^p$ is either $2$ , $7$ , or $1 \pmod p$ .
Proof. Consider a prime $r$ which divides $11^p+17^p$ . Evidently $r \ne 17$ . Apparently, $(-11/17)^p \equiv 1 \pmod r$ , so either $-11/17 \equiv 1 \pmod r$ meaning $r \mid 28$ , or $-11/17$ has order $p$ , as needed. $\blacksquare$
Thus, we find $3p^{q-1}+1$ is the product of $2$ , $7$ , and $1 \pmod p$ primes. We now consider some new cases:

If $p \ne 7$ and $q \ne 2$ , then $3p^{q-1}+1 \equiv 4 \pmod 8$ , while $\nu_7(11^p+17^p) = 1$ . Thus, we must have $3p^{q-1} + 1 = 2^2 \cdot 7^{0\text{ or }1} \cdot \left( \text{$1 \bmod p$ primes} \right).$ This gives that either $1 \equiv 4 \pmod p$ or $1 \equiv 28 \pmod p$ , but this gives $p = 3$ .
If $p = 7$ , the same analysis holds except that the exponent of $7$ must be exactly equal to $0$ (despite $\nu_7(11^p+17^p)=2$ ).
If $q=2$ , the same argument works except that we need the additional observation that $11^p+17^p \not\equiv 0 \pmod 8$ ; hence $3p + 1 = 2^{1\text{ or }2} \cdot 7^{0\text{ or }1} \cdot \left( \text{$1 \bmod p$ primes} \right).$ Hence we have one extra case $(p,q) = (13,2)$ to check, which fails.

This gives a complete proof that $(p,q) = (3,3)$ is the only solution.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

126 posts

#19 h Jan 11, 2021, 7:27 PM • 1 Y

Y by samrocksnature

microsoft_office_word wrote:

Find all primes $p$ and $q$ such that $3p^{q-1}+1$ divides $11^p+17^p$

Proposed by Stanislav Dimitrov,Bulgaria

For $p = 2$ there are no solutions. We begin like v_enhance, so if $q \lvert 11^p + 17^p$ , then $q = 2, 7$ or $q \equiv 1 \pmod{p}$ . Looking at $\pmod{32}$ , there are no solutions so $2^4$ is maximum value of $\nu _ 2(3p^{q-1} + 1)$ and similarly $\nu _ 3(3p^{q-1} + 1) \leq 1$ . Now, annoying casework gives $(p, q) = \boxed{(3, 3)}$ as the only solutions.

This post has been edited 1 time. Last edited by JapanMO2020, Jan 11, 2021, 7:29 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

180 posts

#20 h Apr 1, 2021, 5:00 AM • 1 Y

Y by samrocksnature

arshiya381 wrote:

Aryan-23 wrote:

Illuzion wrote:

why $m \leq 1$ ?

Hamel wrote:

$LTE$ yields that

Can someone please elaborate this ?? I am new to LTE ....
I mean how do we bound $\nu _{(7)} 3p^{q-1}+ 1$

you dont!
you use LTE to show V7 of the right hand side is 1.
so the left hand side can not be devisible by 49.

how do you get $\nu_7(11^p+17^p) = 1$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5001 posts

#21 h Aug 30, 2021, 3:31 PM

Y by

The answer is $(p,q)=(3,3)$ only, which clearly works. We can verify that for $p=2$ no solutions exist, and for $p=3$ we only have $q=3$ . Henceforth assume $p>3$ We now begin with the following important claim:

Claim: If a prime $n$ divides $11^p+17^p$ , then $n=2,7$ or $n \equiv 1 \pmod{2p}$ .
Proof: Let $n$ be such a prime. Clearly $n \neq 11,17$ . Then we have
$11^p+17^p \equiv 0 \pmod{n} \implies \left(\frac{11}{17}\right)^p \equiv -1 \pmod{n} \implies \left(\frac{11}{17}\right)^{2p} \equiv 1.$ For convenience, let $a=\tfrac{11}{17}$ . Then we have $\mathrm{ord}_n(a) \mid 2p$ but $\mathrm{ord}_n(a) \nmid p$ , so either $\mathrm{ord}_n(a)=2$ or $\mathrm{ord}_n(a)=2p$ . If the former is true, then we have $\tfrac{11}{17} \equiv -1 \pmod{n} \implies 28 \equiv 0 \pmod{n}$ , which gives $n \in \{2,7\}$ . If the latter is true, then since $\mathrm{ord}_n(a) \mid n-1$ , we have $p \mid 2p \mid n-1 \implies n \equiv 1 \pmod{p}$ , which is the desired conclusion. $\blacksquare$

Since $3p^{q-1}+1$ is a divisor of $11^p+17^p$ , it follows that $3p^{q-1}+1$ is the product of $2,7$ and primes $1 \pmod{2p}$ . Further, we have
$11^p+17^p \equiv 3^p+1 \equiv 4 \pmod{8}$ as $p$ is odd, so $\nu_2(11^p+17^p)=2$ . Now suppose that $q \neq 2$ . In this case, $q-1$ is even, so $3p^{q-1}+1 \equiv 3+1 \equiv 0 \pmod{4}$ , so we require $\nu_2(3p^{q-1}+1)=2$ . Further, by exponent lifting we have $\nu_7(11^p+17^p)=\nu_7(28)+\nu_7(p)$ , so it follows that
$3p^{q-1}+1=4\cdot 7^\epsilon\cdot P,$ where $P$ is the product of primes that are $1 \pmod{2p}$ and $\epsilon \in \{0,1\}$ —this is because if $p \neq 7$ we have $\nu_7(11^p+17^p)$ and if $p=7$ we have $7 \nmid 3p^{q-1}+1$ anyways. Note that $P \equiv 1 \pmod{2p}$ . Now taking $\pmod{p}$ , we have $3p^{q-1}+1 \equiv 4\cdot 7^\epsilon \pmod{p}$ , which is either $4$ or $28$ . But we also have $3p^{q-1}+1 \equiv 1 \pmod{p}$ , so either $p \mid 3$ or $p \mid 27$ , giving $p=3$ . Since we supposed $p>3$ this case gives no additional solutions
If $q=2$ , then we need $\nu_2(3p^{q-1}+1) \in \{1,2\}$ . Similarly to the previous case, if $p=7$ then $7 \nmid 3p^{q-1}+1$ , otherwise we have $\nu_7(3p^{q-1}+1)\leq 7$ , so
$3p^{q-1}+1=2\cdot2^{\epsilon_1}\cdot 7^{\epsilon_2}\cdot P,$ where $P$ is the product of primes $1 \pmod{2p}$ and $\epsilon_1,\epsilon_2 \in \{0,1\}$ . LIke the previous case, this means that at least one of $\{2,4,14,28\}$ is $1 \pmod{p}$ , but these respectively imply that $p \mid 1, p \mid 3, p \mid 13, p \mid 27$ . Since $p>3$ , the only possibility is therefore $p=13$ . But we can manually check that $(p,q)=(13,2)$ fails, so $(3,3)$ is the only solution. $\blacksquare$

This post has been edited 1 time. Last edited by IAmTheHazard, Aug 30, 2021, 3:41 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1481 posts

CT17

#22 h Apr 5, 2022, 5:15 PM

Y by

Let $r$ be any prime dividing $3p^{q-1} + 1$ . Clearly $r\neq 11,17$ . Hence, we can write $a\equiv \frac{17}{11}\pmod{r}$ so that $a^p\equiv -1\pmod{r}$ . It follows that $\text{ord}_r(a)\in\{2, 2p\}$ , so either $r| 28$ or $r\equiv 1\pmod{2p}$ . We have several cases.

Case 1: $q = 2$ . We can manually verify that $p = 2$ does not work, so $p$ is odd. Moreover, clearly $2p+1$ does not divide $3p+1$ , so the only prime divisors of $3p+1$ are $2$ and $7$ . If $49 | 3p+1$ , then $p\neq 7$ so $7 || 11^p + 17^p$ by LTE, a contradiction. Hence, $v_7(3p + 1) \le 1$ . But since $p$ is odd, $v_2(3p+1)\le v_2\left(11^p + 17^p\right) = v_2(11 + 17) = 2$ . Combining these results, we obtain $3p + 1 | 28$ . However, the only solution to this is $p = 2$ , which we have already checked.

Case 2: $p = 2$ . We can manually verify that there are no solutions in this case.

In all remaining cases, $p$ and $q$ are odd and consequently $3p^{q-1} + 1\equiv 4\pmod{8}$ .

Case 3: $p = 3$ . We can manually verify that the only solution in this case is $q = 3$ .

Case 4: $p = 7$ . Then $7$ does not divide $3p^{q-1} + 1$ , so $\frac{3\cdot 7^{q-1} + 1}{4}\equiv 1\pmod{7}$ , a contradiction.

Case 5: $q\neq 2$ and $p\not\in \{2,3,7\}$ . By LTE, $v_7\left(11^p + 17^p\right) = v_7(11+17) = 1$ . It follows that either $\frac{3p^{q-1} + 1}{4}$ or $\frac{3p^{q-1} + 1}{28}$ is equivalent to $1$ mod $p$ , a contradiction as $p\neq 3$ .

In summary, the only solution is $(p,q) = \boxed{(3,3)}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7585 posts

#23 h Oct 9, 2022, 7:54 PM

Y by

wait is the condition that q is prime necessary (other than, say, parity and divisibility reasons)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1922 posts

#24 h Feb 22, 2023, 8:18 PM

Y by

Note: All of the $\left(\frac{11}{17}\right)$ 's in the proof are the actual fraction, not the value of the Legendre/Jacobi symbol.

Lemma 1. Let $r$ be a prime that divides $3p^{q-1}+1$ . Then $r\in\{2,7\}$ or $r\equiv 1\pmod{2p}$ .
Proof. $r=17$ obviously fails, so $r\mid\left(\frac{11}{17}\right)^p+1.$ If we let $a=\text{ord}_r\left(\frac{11}{17}\right)$ , we have $a\mid 2p$ . Also, we have that $a\nmid p$ unless $r=2$ (which is one of the cases anyway), so $a\in\{2,2p\}$ . If $a=2$ , then $r\mid \left(\frac{11}{17}\right)^2-1\rightarrow r\mid 121-289\rightarrow r\mid 168\rightarrow r\in\{2,3,7\}.$ But $r=3$ would imply $a=1$ , so $r\in\{2,7\}$ . Otherwise, $a=2p$ , so $2p\mid r-1$ , completing our proof.

Lemma 2. If $q\ne 2$ , then $p\in\{2,3\}$ .
Proof. Suppose that $p\ne 2$ . Since $q$ is odd, $p^{q-1}$ is a square, so let $b^2=p^{q-1}$ and $b\in\mathbb{Z}^+$ . Taking mod $8$ , we have
$\nu_2\left(3b^2+1\right)=2.$ Also,
$\nu_7\left(3b^2+1\right)\le \nu_7\left(11^p+17^p\right)=1+\nu_7(p)=\begin{cases}1&p\ne7\\2&p=7\end{cases}.$ Thus $1\equiv 3b^2+1\pmod p$ has to be equivalent to at least one of $2^2$ , $2^2\cdot 7$ , and $2^2\cdot 7^2$ mod $p$ . So $p\mid 3$ , $p\mid 27$ , or $p\mid 195$ . Since $7\nmid 195$ , that case doesn't work, so $p=3$ , which is what we wanted.

Lemma 3. If $q=2$ , then $\nu_2(3p+1)\le 3$ and $\nu_7(3p+1)\le 2$ .
Proof. We have the following by LTE:
$\nu_2(3p+1)\le\nu_2\left(11^p+17^p\right)\le\nu_2(11+17)+\nu_2(p)\le 3$ $\nu_7(3p+1)\le\nu_7\left(11^p+17^p\right)\le\nu_7(11+17)+\nu_7(p)\le 2.$
It then remains to casework using the cases from lemma 2.
Case 1, $p=2$ : Then $11^2+17^2=121+289=410$ , so $3\cdot 2^{q-1}+1\in\{1,2,5,10,41,82,205,410\}.$ Then $2^{q-1}\in\{0,3,27,68\},$ so there are no solutions in this case.

Case 2, $p=3$ : Then
$11^3+17^3=(11+17)\left(17^2-11\cdot 17+11^2\right)=28\cdot 223.$ Therefore,
$3^q+1\in\{1,2,4,7,14,28,223,446,892,1561,3122,6244\}.$ We can see that
$3^q\in\{0,1,3,6,13,27,222,445,891,1560,3121,6243\}\rightarrow 3^q\in\{3,27\}.$ But $q=1$ is not a prime, so only $(p,q)=(3,3)$ works here.

Case 3, $q=2$ : Then $3p+1\mid 11^p+17^p.$ By lemma 1, all prime factors of $3p+1$ are either $2$ , $7$ , or $1$ mod $2p$ . In the third case, $4p+1$ is too big, so $2p+1\mid 3p+1$ , absurd. So
$3p+1=2^m 7^n$ for nonnegative integers $m,n$ where $m\le 3$ and $n\le 2$ (by lemma 3). Therefore,
$3p+1\in\{1,2,4,8,7,14,28,56,49,98,196,392\}.$ This implies that
$p\in\{0,1,2,9,16,65\},$ all of which are impossible.

Combining all cases, our answer is just $(p,q)=\boxed{(3,3)}$ , which obviously works. QED.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8866 posts

#25 h Apr 9, 2023, 3:11 AM

Y by

This is such an incredibly boring but also slightly difficult problem.

Let $p_1$ be a prime that divides $3p^{q-1} + 1$ . Then as $p_1 \mid 11^p + 17^p$ , either $p_1 \equiv 1 \pmod p$ or $p_1 \mid 28$ .

The rest of the problem is finding constraints on $\nu_2(3p^{q-1} + 1)$ . Notice that if $p, q$ are both odd primes, then $\nu_2(3p^{q-1} + 1) = 2$ precisely. On the other hand, $2$ is not a quadratic residue mod $7$ , so this means that $7 \nmid 3p^{q-1} + 1$ . But this means now that $4 \equiv 1 \pmod p$ as $3p^{q-1} + 1 \equiv 1 \pmod p,$ so $p=3$ , and correspondingly $q = 3$ too.

Now if $q = 2$ , then note that $\nu_2(3p+1) \leq 2$ and $\nu_7(3p+1) \leq 1$ , which upon a finite case check yields no solutions.

Thus $(3, 3)$ is the only solution.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8 posts

#27 h Sep 25, 2023, 2:27 PM

Y by

HamstPan38825 wrote:

Notice that if $p, q$ are both odd primes, then $\nu_2(3p^{q-1} + 1) = 2$ precisely.

No. Try $p=3$ , $q=7$ for example

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

682 posts

#28 h Dec 29, 2023, 1:38 AM

Y by

Very hard. What.

Assume that $p$ and $q$ are odd primes. Note that $\nu_2(3p^{q-1} + 1) = 2$ and hence due to size reasons we must have an odd prime factor $r$ . Now consider a prime factor of $11^p + 7^p$ , say $t$ . Then we have,
$\begin{align*} \left(\frac{-11}{7}\right)^{2p} &\equiv 1 \pmod{t} \end{align*}$ Then we have $\text{ord}_t(-11 \cdot 7^{-1}) \mid 2p$ . Then either $-11 \equiv 7 \pmod{t}$ and hence $t \mid 28$ , or we have $2p \mid t - 1 \iff t \equiv 1 \pmod{2p}$ . Then all prime factors of $11^p + 7^p$ are $1$ , $2$ or $7$ modulo $2p$ . As a result all prime factors of $3p^{q-1} + 1$ are equal to $2$ or $7$ or are congruent to $1$ modulo $2p$ . Now note that $\nu_7(3p^{q-1} + 1) \leq 1$ as if $p \neq 7$ it is easy to see that $\nu_7(11^p + 17^p) = 1$ else if $p = 7$ , then $\nu_7(3 \cdot 7^{q-1} + 1) = 0$ . Assume $7 \mid 3p^{q-1} + 1$ . However then,
$\begin{align*} 3p^{q-1} + 1 \equiv 0 \pmod{7}\\ p^{q-1} \equiv 2 \pmod{7} \end{align*}$ However as $2$ is a NQR modulo $7$ we cannot have $7 \mid 3p^{q-1} + 1$ . Thus $3p^{q-1} + 1 = 4 \cdot P$ where $P$ is the product of primes congruent to $1$ modulo $2p$ . However then obviously we require $3p^{q-1} + 1 \equiv 4 \pmod{p}$ or $3 \equiv 0 \pmod{p}$ and hence $p = 3$ . Now we then have,
$\begin{align*} 3^q + 1 \mid 11^3 + 17^3 \end{align*}$ from which we find $q = 3$ . Now if $q = 2$ we find,
$\begin{align*} 3p + 1 \mid 11^p + 17^p \end{align*}$ Note that from our claim the primes dividing $3p+1$ are $2$ , $7$ or are $1$ modulo $2p$ . Clearly $2p + 1 \nmid 3p + 1$ and we require $\nu_p(3p + 1) \leq 7$ and $\nu_p(3p + 1) = 2$ . Hence $3p + 1 = 2^x7^y$ and a finite case check leads to no solutions.

This post has been edited 2 times. Last edited by Shreyasharma, Dec 29, 2023, 1:40 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2534 posts

#29 h Feb 12, 2024, 8:26 PM

Y by

The answer is $\boxed{(p,q)=(3,3)}$ , which clearly works.

Claim 1: Let $r$ be a prime that divides $3p^{q-1}+1$ . Either $r=2$ , $r=7$ , or $r \equiv 1 \pmod{2p}$ .

Proof: $r$ obviously cannot be $17$ , and $r=2$ clearly works, so assume $r \neq 2, 17$ for the remainder of this proof. We write

$r \mid \left(\frac{11}{17}\right)+1,$
meaning the order of $\left(\frac{11}{17}\right)$ modulo $r$ divides $2p$ ; denote this order as $o$ Furthermore, $o$ does not divide $p$ , so $o$ can be $2$ or $2p$ . If $o=2$ ,

$\left(\frac{11}{17}\right)^2 \equiv 1 \pmod{r} \implies -168 \equiv 0 \pmod{r} \implies r \in \{3,7\}.$
Manually checking each case gives a contradiction for $r=3$ , so $r=7$ is the only extra case here.

If $o=2p$ , we have $2p \mid r-1$ , which gives the last solution set. $\square$

Claim 2: If $p, q \neq 2$ , then $p=3$ .

Proof: Suppose that $p \neq 7$ . Let $a$ be the positive integer such that $a^2 = p^{q-1}$ . Notice that

$3a^2+1 \equiv 4 \pmod{8}.$
Also,

$\nu_7(3a^2+1) \le \nu_7(11^p+17^p) = 1+ \nu_7(p) =1.$
Some quick analysis yields

$3a^2+1 \equiv 2^2, 2^2 \cdot 7 \pmod{p}$ $\implies 1 \equiv 4 \pmod{p} \ \textbf{ or } \ 1 \equiv 28 \pmod{p}.$
This implies that $p=3$ . If $p=7$ , we must analogously have

$1 \equiv 196 \pmod{p},$
a contradiction. $\square$

Now, we break this problem into cases:

If $p=2$ , we have

$3 \cdot 2^{q-1}+1 \mid 410$ $\implies 2^{q-1} \in \{0,3,27,68\},$
which is impossible.

If $p=3$ , we have

$3^q+1 \mid 6244$ $\implies 3^q \in \{0,1,3,6,13,27,222,445,891,1560,3121,6243\}.$
This makes the only solution $q=3$ .

If $q=2$ , we have

$3p+1 \mid 11^p+17^p.$
Claim 1 gives us that the only prime factors of $3p+1$ are $2$ , $7$ , or $2kp+1$ for some positive integer $k$ . Clearly, the latter case is out of the question, so we have that

$3p+1 = 2^m7^n.$
Notice that

$\nu_2(3p+1) \le \nu_2(11^p+17^p) \le 3$ $\nu_2(3p+1) \le \nu_2(11^p+17^p) \le 2.$
At this point, there are a finite amount of values for $3p+1$ , which yield

$p\in\{0,1,2,9,16,65\},$
after some computation. This is a contradiction, so there are no solutions in this case either.

Adding up all the solutions from the three cases gives the desired answer.

This post has been edited 1 time. Last edited by joshualiu315, Feb 12, 2024, 8:27 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2502 posts

ATGY

#30 h Jul 24, 2024, 9:21 PM

Y by

We will deal with the cases $q = 2$ , $p = 2$ , and $p = 7$ later, so assume none of these are true.

\textbf{Claim 1:} If $r$ is a prime such that $r \mid 3p^{q - 1} + 1$ , then $r \equiv 1 \mod{p}$ or $r \mid 28$ .

$r \mid 3p^{q - 1} + 1 \implies 11^p + 17^p \equiv 0 \mod{r} \implies \left(\frac{-11}{17}\right)^p \equiv 1 \mod{r}$
Let $k$ be the order of $\frac{-11}{17} \mod r$ . We have $k \mid (p, r - 1) = 1, p$ . If $k = 1$ , then

$r \mid \frac{-11}{17} - 1 \implies r \mid 28 \implies r = 2, 7$
If $(p, r - 1) = p$ , we have $p \mid r - 1 \implies r \equiv 1 \mod{p}$ .

\textbf{Claim 2:} $v_2(3p^{q - 1} + 1) = 2$

Since $q - 1$ is even and $p$ is odd,

$p^{q - 1} \equiv 1 \mod{8} \implies 3p^{q - 1} + 1 \equiv 4 \mod{8}$
So let

$3p^{q - 1} + 1 = 2^2 \cdot 7^\alpha \cdot p_1^{\alpha_1} \cdots p_k^{\alpha_k}$
where $p_1 \equiv p_2 \equiv \cdots \equiv p_k \equiv 1 \mod{p}$ .

\textbf{Claim 3:} $p = 3$ , $q = 3$

From LTE, we have

$v_7(11^p + 17^p) = v_7(28) + v_7(p) = 1$
Therefore $\alpha = 0, 1$ , and

$2^2 \cdot 7^\alpha \cdot p_1^{\alpha_1} \cdots p_k^{\alpha_k} \equiv 28, 4 \equiv 1 \mod{p}$
So $p \mid 27, 3 \implies p = 3$ .

So, we have

$3^q + 1 \mid 11^3 + 17^3 = 6244 = 7 \cdot 4 \cdot 223$
which quickly yields $q = 3$ .

If $p = 2$ , we have

$3 \cdot 2^q + 1 \mid 11^2 + 17^2 = 410$
which yields no solutions.

If $q = 2$ , we have

$3p + 1 \mid 11^p + 17^p$
Here, $v_2(3p + 1) = 1$ , which means $14 \equiv 1 \mod{p}$ , or $p = 13$ , and $q = 2$ , which doesn't work.

If $p = 7$ ,

$v_7(11^p + 17^p) = 2$
so the power of 7 in $3p^{q - 1} + 1$ can be $0, 1, 2$ , where $0, 1$ yield the same cases as earlier and $2$ yields

$196 \equiv 1 \mod{p} \implies p \mid 195$
which is impossible as $7 \nmid 195$ .

So, our only solution is $(3, 3)$ .

This post has been edited 1 time. Last edited by ATGY, Jul 24, 2024, 9:22 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

60 posts

kotmhn

#31 h Sep 13, 2024, 11:44 AM

Y by

Let $r$ be a prime factor of $3p^{q-1}+1$ . Then we have that either $r = 7$ or $r\equiv 1 \pmod{p}$
Now observe that if $r_1,r_2, \dots r_i$ be all the prime factors of $3p^{q-1}+1$ we have that all $r_i \equiv 1 \pmod{p}$ .
But then as $3p^{q-1}+1 = r_1^{\alpha_1}r_2^{\alpha_2}\dots r_i^{\alpha_i} = (pk_1 + 1)^{\alpha_1}(pk_2)^{\alpha_2}\dots (pk_i)^{\alpha_i}$
Here if prime factors is greater than $3$ then we have that the term with $p$ in the product on RHS is even while on LHS it is odd contradiction.
Hence only $2,3,7$ can be the prime factors of $3p^{q-1}+1$ , then a case bash gives $(3,3)$ as the only solution.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

268 posts

L13832

#32 h Oct 29, 2024, 2:49 PM • 2 Y

Y by alexanderhamilton124, Nobitasolvesproblems1979

Take a prime $r$ such that it divides $3p^{q-1}+1$ so $\text{ord}_{r}\left(\frac{11}{17}\right)=2$ or $2p$ , so $r=2,7$ or $r\equiv 1 \pmod{2p}$ .
Note that if $7\mid3p^{q-1}+1$ then we get $p^{q-1}\equiv 2\pmod{7}$ which is not possible.
Now, $\nu_7(11^p+17^p)=\nu_7(28)+\nu_7(p)=1$ . We check for $p=2$ which gives us $3\cdot 2^{q-1}+1\mid 410$ which is not possible. For $p=3$ we have $3^q+1\mid 6244$ , after case-bash we get $q=3$ .
If $p\neq7$ then we have $\nu_7(11^p+17^p)=1$ , if $p=7,$ then $\nu_7(3\cdot 7^{p-1}+1)=0$ . So $3p^{q-1}+1\equiv 2^2\cdot 7, 2^2\pmod{p}$ , this gives us $(p,q)=(3,3)$ to be a solution.
For $q=2$ we have $3p+1\mid 11^p+17^p$ , since $3p+1$ cannot be written as $1\pmod{2p}$ , so it is of the form $2^i7^j$ , also we can write it as $3p+1\mid 11^p+17^p$ and because $\nu_2(3p+1)=1$ we have $p=13\implies q=2$ , which does not work.
So our only answer is $\boxed{(p,q)=(3,3)}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

46 posts

#33 h Nov 7, 2024, 8:31 PM • 1 Y

Y by S_14159

Only solution is (3,3)

Let $r$ be a prime dividing $3p^{q-1}+1$ , then we get by taking the inverse $\frac{11^p}{17^p}$ congruent to 1, giving either $r$ being $2,7$ or 2p divides r-1, for the second case, $3p^{q-1}+1$ is congruent to $1$ modulo 2p, which is impossible for p odd prime. Using LTE on $11^p+17^p$ for $7$ , we get that, the most $7$ power is 1 and $8$ can never divide $11^p+17^p$ , this means that $3p^{q-1}+1 = 7.2^n$ where $n \leq 2$ , check the remaining cases.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1354 posts

#34 h Nov 12, 2024, 6:33 AM

Y by

Take any prime $r \geq 3$ which divides $3p^{q-1}+1$ , so $r \mid 11^p + 17^p$ and thus $\text{ord}_{r}\left(11 \cdot 17^{-1}\right)=2$ or $2p$ , giving $r=2,7$ or $r\equiv 1 \pmod{2p}$ .

Suppose $p\geq 3$ . Then $\nu_2(11^p + 17^p) = 2$ (by mod $8$ ) and $\nu_7(11^p + 17^p) = \nu_7(28) + \nu_7(p)$ (by Lifting the Exponent) which is $1$ if $p\neq 7$ and $2$ if $p=7$ . So $\nu_7(3p^{q-1} + 1) \leq 1$ (for $p=7$ actually it is $0$ ) and $\nu_2(3p^{q-1} + 1) \leq 2$ Hence $3p^{q-1} + 1 = 2^{\leq 2}7^{\leq 1} \ \cdot \ (\mbox{primes } \equiv 1 \pmod{2p}).$ Taking the latter mod $p$ yields $p = 2, 3, 13$ . Since $11^2 + 17^2 = 2 \cdot 5 \cdot 41$ , checking $3 \cdot 2^{q-1} + 1 \mid 5 \cdot 41$ gives no solution. For $11^3 + 17^3 = 28 \cdot (17^2 - 17 \cdot 11 + 11^2) = 2^2 \cdot 7 \cdot 223$ checking $\displaystyle \frac{3^{q}+1}{2} \mid 2\cdot 7 \cdot 223$ gives $q=3$ , so $(3,3)$ is a solution. If $p=13 = 2\cdot 7 - 1$ , then the right-hand side above must be divisible by $7$ , but then mod $7$ yields $3\cdot (-1)^{q-1} + 1 \equiv 0$ , contradiction for any positive integer $q$ .

Remark. We did not use anywhere that $q$ is prime!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5610 posts

#35 h Jan 4, 2025, 1:44 PM

Y by

Solved a while ago but forgot to post

The only solution is $\boxed{(p,q) = (3,3)}$ , which works.

Claim: Any prime divisor $r\mid 11^p + 17^p$ satisfies $r\in \{2,7\}$ or $r\equiv 1\pmod{2p}$ .
Proof: Let $r$ be a prime divisor of $11^p + 17^p$ and $r\ne 2,7$ .

We have $11^p + 17^p \equiv 0\pmod r$
This implies that $\left(\frac{11}{17}\right)^{p}\equiv -1\pmod r,$ so $\left(\frac{11}{17}\right)^{2p}\equiv 1\pmod r$
Thus $\mathrm{ord}_r \left(\frac{11}{17}\right)$ divides $2p$ but not $p$ , so it must be either $2$ or $2p$ .

If $\mathrm{ord}_r \left(\frac{11}{17}\right) = 2$ , then we have $r\mid 17^ 2- 11^2 = 168$ Since $r$ is odd, $\frac{11}{17} \not\equiv 1\pmod r$ , so $r\ne 3$ . This implies $r=7$ , which we assumed to not be true.

If $\mathrm{ord}_r\left(\frac{11}{17}\right) = 2p$ , then $2p\mid r-1$ , $r\equiv 1\pmod{2p}$ , as desired. $\square$

Claim: $p\ne 2,7$
Proof: If $p=2$ , then $3\cdot 2^{q-1} + 1 \mid 410$ It's easy to check this is not possible.

If $p=7$ , then $3\cdot 7^{q-1} + 1 \mid 11^7 + 17^7$ Since $22\nmid 11^7 + 17^7$ , $q=2$ doesn't work. Now assume $q$ is odd. We have $\nu_2(3\cdot 7^{q-1} + 1) = 2$ . So any prime factor of $\frac{3\cdot 7^{q-1} + 1}{4}$ is $1\pmod{14}$ , which implies $3\cdot 7^{q-1} + 1\equiv 4\pmod{14}$ , absurd. $\square$

If $p=3$ , then $3^q + 1 \mid 11^3 + 17^3 =6244$ One can manually check that this is not the case since $3^q < 6244\implies q\le 7$ .

From now on, assume $p\not\in \{2,3,7\}$ .

Case 1: $q=2$
Then we have $3p+1 \mid 11^p + 17^p$ Note that no prime that if $1\pmod{2p}$ divides $3p+1$ , so the only prime factors of $3p+1$ are $2$ and $7$ . However $1\le \nu_2(3p+1) \le \nu_p(11^p + 17^p) = 2$ and $\nu_7(3p+1)\le \nu_7(11^p + 17^p) = 1$ by LTE. So $3p+1\in \{2,4,14,28\},$ all of which don't work.

Case 2: $q>2$
Then $p^{q-1}\equiv 1\pmod 4$ , so $4\mid 3\cdot p^{q-1} + 1$ . Thus by Claim 15.1, $3\cdot p^{q-1} + 1\equiv \{4,28\}\pmod{2p}$ However, $3\cdot p^{q-1} + 1\equiv p+1\pmod{2p},$ so $p=3$ , contradiction.

This post has been edited 1 time. Last edited by megarnie, Jan 4, 2025, 1:45 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

656 posts

#36 h Apr 26, 2025, 12:06 AM

Y by

I claim the answer is $(p, q) = \boxed{(3, 3)}.$ It is easy to check $p = 2,3,$ so we will assume that $p\geq5.$

First, I claim that if a prime $r$ satisfies $r\mid11^p + 17^p,$ then either $r = 2, 7,$ or $r\equiv1\pmod p.$

By taking modulo $r,$ we have that $\left(\frac{11}{17}\right)^{2p}\equiv1\pmod r\implies\operatorname{ord}_{r}\left(\frac{11}{17}\right)\mid(2p, r - 1)\mid2p.$ If the order is $2,$ we have that $11 + 17 \equiv 0\pmod r \implies r=2, 7.$ If the order is $2p,$ this works, and $r \equiv1\pmod p.$

Note that we can write $3p^{q - 1} + 1 = 4^k7^mt,$ where $t$ is a product of primes that are $1\pmod p.$ We can easily see that $k\leq1$ by taking modulo 8.

If $p\neq7, q\neq2,$ we have that $1 \equiv 4\cdot 7^m \pmod p$ . We also know that $m \leq 1$ by taking $\nu_7(11^p + 17^p) = 1 + \nu_7(p) = 1.$ Thus, $p = 3.$

If $p = 7,$ then $3\cdot7^{q - 1} + 1 = 4t.$ By taking modulo $7$ , there is a contradiction.

If $q = 2,$ then $3p+1=2^{1\text{ or }2}7^{0\text{ or }1}t.$ By taking modulo $p,$ we have that $p = 13$ is possible. However, this is impossible.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a