number theory from China TST

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

number theory from China TST

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: China TST 4 Problem 4

The post below has been deleted. Click to close.

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

29 posts

#1 h Mar 22, 2017, 3:52 PM • 6 Y

Y by rightways, laegolas, anantmudgal09, Hypernova, Adventure10, Mango247

Given integer $d>1,m$ ,prove that there exists integer $k>l>0$ , such that $(2^{2^k}+d,2^{2^l}+d)>m.$

Z K Y

The post below has been deleted. Click to close.

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

776 posts

#2 h Mar 22, 2017, 4:12 PM • 1 Y

Y by Adventure10

fantastic problem

Z K Y

The post below has been deleted. Click to close.

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

143 posts

Erkhes

#3 h Mar 22, 2017, 4:55 PM • 3 Y

Y by Hypernova, Adventure10, Mango247

solution pls

Z K Y

The post below has been deleted. Click to close.

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

1963 posts

ABCDE

#4 h Mar 22, 2017, 5:47 PM • 2 Y

Y by Adventure10, Mango247

Take $l>\log_2d$ and consider a prime factor $p$ of $2^{2^l}+d$ such that $p\not\equiv1\pmod{2^l}$ . Such a $p$ must exist, or $2^{2^l}+d\equiv1\pmod{2^l}\implies 2^l\mid d-1$ , a contradiction as $1<d<2^l$ . Now, let $p-1=2^ab$ for some odd $b$ and $a<l$ and set $k=l+\text{ord}_b2$ . We now have that $p-1\mid 2^k-2^l$ as it is divisible by both $2^a$ and $b$ , so $p\mid 2^{2^k}-2^{2^l}$ and $p\mid 2^{2^k}+d$ . Now it suffices to show that there are arbitrarily large primes that divide a number of the form $2^{2^n}+d$ , as by the above argument we may take such a large prime greater than $m$ that divides $2^{2^N}+d$ for some $N>l$ . This is a well-known Iran TST problem, and you can see here: https://artofproblemsolving.com/community/c6h275813p1492629 for the proof.

Z K Y

The post below has been deleted. Click to close.

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

113 posts

#5 h Mar 22, 2017, 5:48 PM • 2 Y

Y by Adventure10, Mango247

You can prove this method: Prove that 2^(2^l)+d have infinity primes as its divisors when l goes to infinity

Z K Y

The post below has been deleted. Click to close.

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

1000 posts

#6 h Mar 22, 2017, 6:48 PM • 2 Y

Y by Adventure10, Mango247

Just Kobayashi's theorem.

Z K Y

The post below has been deleted. Click to close.

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

1135 posts

#8 h Mar 23, 2017, 4:57 AM • 1 Y

Y by Adventure10

Unless I am mistaken, it seems that all of the proofs above only prove that there are infinitely many primes dividing the terms. However, there can be infinitely many primes dividing the terms, just each prime divides at most one term. So, it is possible that there are only finitely many primes $\not\equiv 1 \pmod { 2^l}$ , in which case ABCDE's solution falls apart at the end? I am sorry if I misunderstood your proofs, and please correct me if I am wrong, since I could this infinite prime case the hardest part of this problem.

This post has been edited 1 time. Last edited by MathPanda1, Mar 23, 2017, 4:57 AM

Z K Y

The post below has been deleted. Click to close.

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

824 posts

andria

#9 h Mar 23, 2017, 8:10 AM • 2 Y

Y by Adventure10, Mango247

ABCDE wrote:

$2^{2^l}+d\equiv1\pmod{2^l}\implies 2^l\mid d-1$

Obviously this part is wrong if $2\mid d$ .

Z K Y

The post below has been deleted. Click to close.

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

224 posts

#10 h Mar 23, 2017, 8:20 AM • 2 Y

Y by Kaguyaximei, Adventure10

Let $S=\{ p \textrm { a prime } : p|2^{2^n}+d \textrm { for some n } \}$ . $S$ is infinite. Assume that there is a positive integer $m$ such that $(2^{2^k}+d,2^{2^l}+d)< m$ for all pairs $(k,l)$ of distinct positive integers. Let $S_1=\{p\in S|p< m\}$ and $S_2=\{p\in S|p\geq m\}$ . There is a positive integer $X$ such that $v_p(2^{2^n}+d)<X$ for all $n\in\mathbb{N}$ and $p\in S_1$ , otherwise there is a prime in $S_1$ with a very large power that divides two distinct terms of $2^{2^n}+d$ . Any prime divisor of $S_2$ divide $2^{2^n}+d$ for exactly one $n$ . Let $p\in S_2$ a divisor of $2^{2^n}+d$ . Note that the congruence $2^k\equiv 2^n\pmod{p-1}$ has infinitely many solution $k>n$ if $2^{n+1}\not|p-1$ . Therefore by our assumption we must have $p\equiv 1\pmod{2^{n+1}}$ . Take $n$ very large so that $2^{n+1}>d+\left(\prod_{q\in S_1}q\right)^X$ . Let $\alpha_q$ be the largest power of $q$ that divide $2^{2^n}+d$ . By our previous observation $d\equiv \prod_{q\in S_1} q^{\alpha_q}\pmod {2^{n+1}}$ from which we find $d=\prod_{q\in S_1}q^{\alpha_q}$ , since $d>1$ , there is a $q\in S_1$ such that $\alpha_q>0$ . but then $q|2$ . Therefore $d=2^t$ , where $t\in\mathbb{N}$ .
Write $t=2^uv$ for some odd $v$ . It is not hard to prove that the sequence $2^{l-u}-v$ has infinitely many primes dividing at least one of its terms. Let $r>m$ be a prime that divides a term, say $2^{l-u}-v$ , with large $l$ . Let $k=l+r-1$ . Then $2^ur|(2^l-t,2^k-t)$ . Therefore $2^{2^ur}+1|(2^{2^l-t}+1,2^{2^k-t}+1)|(2^{2^m}+2^t,2^{2^k}+2^t)$ , but clearly $2^{2^ur}+1>r>m$ . Contradiction !

This post has been edited 3 times. Last edited by siddigss, Mar 23, 2017, 8:25 AM

Z K Y

The post below has been deleted. Click to close.

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

824 posts

andria

#11 h Mar 23, 2017, 9:31 AM • 9 Y

Y by rightways, WizardMath, tenplusten, rkm0959, Kaguyaximei, Aniruddha07, sabkx, Adventure10, Mango247

Lemma 1: the set of prime divisors of $n^k+c$ is infinite.

proof

Lemma 2: if $a>1$ then $\text{gcd}(a^m+1,a^n+1)=a^{\text{gcd}(m,n)}+1$ for odd $m,n$ .

Consider a large enough integer $l$ then if we can find a prime $p$ such that:
$v_2(p-1)\leq l\ ,\ p>m\ ,\ p\mid 2^{2^l}+d\ \clubsuit$ then:
$2^{l}\stackrel{p-1}{\equiv}2^{l+\phi(p-1)}\Longrightarrow 2^{2^{l}}\stackrel{p}{\equiv}2^{2^{l+\phi(p-1)}}\Longrightarrow 2^{2^{l}}+d\stackrel{p}{\equiv}2^{2^{l+\phi(p-1)}}+d\Longrightarrow \text{gcd}(2^{2^{l}}+d,2^{2^{l+\phi(p-1)}}+d)\geq p>m$ So assume that there isn't any prime with these conditions ( $\clubsuit$ ). hence for any sufficiently large integers $l$ the prime factorization of $2^{2^l}+d$ is in the following form:
$2^{2^{l}}+d=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}(2^{l+1}s_1+1)^{\beta_1}(2^{l+1}s_2+1)^{\beta_2} \dots (2^{l+1}s_t+1)^{\beta_t}$ where $p_1,p_2,\dots ,p_k<m$ .
Assume $M=p_1^{a_1+1}p_2^{a_2+1}\dots p_k^{a_k+1}$ . Since $l$ is sufficiently large for any $s$ :
$2^{l+\phi(\phi(M))s}\stackrel{\phi(M)}{\equiv}2^{l}\Longrightarrow 2^{2^{l+\phi(\phi(M))s}}\stackrel{M}{\equiv}2^{2^{l}}\Longrightarrow 2^{2^{l+\phi(\phi(M))s}}+d\stackrel{M}{\equiv}2^{2^{l}}+d\stackrel{M}{\equiv} p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}(2^{l+1}s_1+1)^{\beta_1}(2^{l+1}s_2+1)^{\beta_2} \dots (2^{l+1}s_t+1)^{\beta_t}$ Hence for any $1\leq i\leq k$ we have:
$v_{p_i}(2^{2^{l+\phi(\phi(M))s}}+d)=a_i$ So we conclude that:
$2^{2^{l+\phi(\phi(M))s}}+d=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}(2^{l+\phi(\phi(M))s+1}u_1+1)^{c_1}(2^{l+\phi(\phi(M))s+1}u_2+1)^{c_2} \dots (2^{l+\phi(\phi(M))s+1}u_r+1)^{c_r}$ now observe that:
$d\stackrel{2^{l+\phi(\phi(M))s+1}}{\equiv}2^{2^{l+\phi(\phi(M))s}}+d\stackrel{2^{l+\phi(\phi(M))s+1}}{\equiv}p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}\Longrightarrow 2^{l+\phi(\phi(M))s+1}\mid d-p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}$ Hence:
$d=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}$ then for any $i$ such that $a_i\geq 1$ we have:
$\left.\begin{array}{ccc} p_i\mid d\\ \\ p_i\mid 2^{2^l}+d=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}(2^{l+1}s_1+1)^{\beta_1}(2^{l+1}s_2+1)^{\beta_2} \dots (2^{l+1}s_t+1)^{\beta_t} \end{array}\right\}\Longrightarrow p_i\mid 2^{2^{l}}\Longrightarrow p_i=2$

Hence $d=2^s$ ( $t\geq 1$ ).

hence for any $m$ we have:

$2^{2^m-s}+1=(2^{m+1}s_1+1)^{j_1}\dots (2^{m+1}s_u+1)^{j_w}$
take a prime $p\mid 2^{2^m-s}+1$ . observe that from lemma there is a large number $q$ and $m$ such that:

$\left.\begin{array}{ccc} q\mid 2^m-s\\ \\ q\mid 2^{m+(q-1)h}-s \end{array}\right\}\stackrel{(2)}{\Longrightarrow} 2^{2^{v_2(s)}q}+1\mid 2^{2^m-s}+1,2^{2^{v_2(s)}q}+1\mid 2^{2^{m+(q-1)h}-s}+1\Longrightarrow \text{gcd}(2^{2^m}+2^s,2^{2^{m+(q-1)h}}+2^s)\geq 2^{2^{v_2(s)}q}+1>m$ (since $q$ is large enough).

Q.E.D

This post has been edited 2 times. Last edited by andria, Mar 23, 2017, 1:16 PM

Z K Y

The post below has been deleted. Click to close.

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

2487 posts

#12 h Mar 23, 2017, 10:28 AM • 3 Y

Y by Gluncho, Adventure10, Mango247

Just to note that Lemma 1 above is a straight consequence of Kobayashi's theorem.

Z K Y

The post below has been deleted. Click to close.

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

112 posts

#13 h Apr 14, 2017, 11:49 AM • 1 Y

Y by Adventure10

WizardMath wrote:

Just to note that Lemma 1 above is a straight consequence of Kobayashi's theorem.

What's Kobayashi's theorem, please? Can't find it on the Internet.

Z K Y

The post below has been deleted. Click to close.

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

402 posts

#14 h Apr 14, 2017, 12:04 PM • 1 Y

Y by Adventure10

$\text{Kobayashi's Theorem}$

Consider a sequence $\{a_n\}_{n\in\mathbb{N}}$ which has only finitely many primes dividing atleast one of its terms. Then the sequence $\{a_n+c\}_{n\in\mathbb{N}}\forall c\in\mathbb{Z}$ has infinitely many primes dividing atleast one of its terms.

This post has been edited 2 times. Last edited by babu2001, Apr 14, 2017, 5:15 PM

Z K Y

The post below has been deleted. Click to close.

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

112 posts

#15 h Apr 14, 2017, 2:48 PM • 2 Y

Y by Adventure10, Mango247

babu2001 wrote:

$\text{Kobayashi's Theorem}$

Consider a sequence $\{a_n\}_{n\in\mathbb{N}}$ which has only finitely many primes dividing atleast one of its terms. Then the sequence $\{a_n+c\}_{n\in\mathbb{N}}\forall c\in\mathbb{Z}$ has infinitely many primes dividing atleast one of its terms.

Thank you. But $c$ can't be zero.

This post has been edited 1 time. Last edited by hutu683, Apr 14, 2017, 2:49 PM

Z K Y

The post below has been deleted. Click to close.

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

327 posts

#18 h Jun 25, 2020, 6:40 AM • 3 Y

Y by mijail, JG666, Ru83n05

Let $a_n=2^{2^n}+d$ . Suppose there exist $m$ and $d$ such that $(a_k,a_l)\leq m$ for all $k$ and $l$ . It follows that if $p^t$ divides $a_k$ and $a_l$ for some positive integers $t$ , $k$ and $l$ , then $p^t<m$ . In other words, $\nu_p(a_k)$ is bounded.

Lemma 1: If positive integers $n$ and $k$ satisfy $\nu_2(k)<n$ , then $k|2^l-2^n$ for some $l>n$ .
Proof: Let $k=2^a b$ , where $b$ is odd. We have $a<n$ . There exists $m$ such that $b|2^m-1$ . Then $2^ab|2^{n+m}-2^n=2^n(2^m-1)$
Lemma 2: If $p|a_n$ for some prime $p>m$ and integral $n$ , then $p\equiv 1\pmod{2^n}$ .
Proof: Suppose $2^n$ does not divide $p-1$ . Then it follows from lemma 1 that $p-1$ divides $2^l-2^n$ for some $l>n$ . Then
$a_l-a_n=2^{2^l}-2^{2^n}=2^{2^n}(2^{2^l-2^n}-1)$ The quantity $2^{2^l-2^n}-1$ is divisible by $p$ because $2^l-2^n$ is divisible by $p-1$ . Then $p\leq (a_n,a_l)\leq m$ , contradiction.

Lemma 3: $d$ is a power of $2$
Proof: For each $n$ we write $a_n=2^{k_n}b_nc_n$ , where $b_n$ contains only odd prime divisors of $a_n$ that are less than $m$ and $c_n$ contains those that are not less than $m$ . It follows from Lemma 2 that $c_n\equiv 1\pmod{2^n}$ , therefore $a_n\equiv d\equiv 2^{k_n}b_n\pmod{2^n}$ . The number of primes less than $m$ is finite and for each of them the sequence $\nu_p(a_n)$ is bounded. Moreover, $k_n=\nu_2(d)$ when $n>\nu_2(d)$ . This means there exists $M$ such that $2^{k_n}b_n<M$ for every integer $n$ , that is, $2^{k_n}b_n=d$ for sufficiently large $n$ .
Thus $d$ divides $a_n=2^{2^n}+d$ for sufficiently large $n$ , which means $d$ is a power of $2$ .

Lemma 4: For large enough $n$ , there exists $l>n$ such that $a_n|a_l$ .
Proof: Let $d=2^k$ . Choose $n>\nu_2(k)$ . Then $\nu_2(2^n-k)=\nu_2(k)$ . It follows from Lemma 1 that there exists $l$ such that $2^n-k|2^l-2^n$ and therefore $2^n-k|2^l-k$ .
Since $\nu_2(2^l-k)=\nu_2(k)=\nu_2(2^n-k)$ , the number $\frac{2^l-k}{2^n-k}$ is odd, and thus $2^{2^n-k}+1$ divides $2^{2^l-k}+1$ . Multiplying by $2^k$ , we get that $a_n|a_l$ .

It follows from Lemma 4 that $a_n=(a_n,a_l)\leq m$ for each $n>\nu_2(k)$ , a contradiction.

This post has been edited 1 time. Last edited by ACGNmath, Jun 25, 2020, 6:42 AM

Z K Y

The post below has been deleted. Click to close.

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

162 posts

#20 h Sep 11, 2020, 6:33 PM • 5 Y

Y by Juanscholtze, Nathanisme, k12byda5h, JG666, sabkx

Soln

This post has been edited 2 times. Last edited by Gaussian_cyber, Sep 11, 2020, 7:31 PM

Z K Y

The post below has been deleted. Click to close.

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

892 posts

#21 h Sep 4, 2021, 7:22 PM

Y by

ACGNmath wrote:

Lemma 2: If $p|a_n$ for some prime $p>m$ and integral $n$ , then $p\equiv 1\pmod{2^n}$ .
Proof: Suppose $2^n$ does not divide $p-1$ . Then it follows from lemma 1 that $p-1$ divides $2^l-2^n$ for some $l>n$ . Then
$a_l-a_n=2^{2^l}-2^{2^n}=2^{2^n}(2^{2^l-2^n}-1)$ The quantity $2^{2^l-2^n}-1$ is divisible by $p$ because $2^l-2^n$ is divisible by $p-1$ . Then $p\leq (a_n,a_l)\leq m$ , contradiction.

$p|2^{2^l-2^n}-1$ does not imply $p|2^{2^n}+d, 2^{2^l}+d$ . How did you get contradiction?

This post has been edited 1 time. Last edited by SerdarBozdag, Sep 4, 2021, 7:22 PM

Z K Y

The post below has been deleted. Click to close.

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

27 posts

#22 h Jan 25, 2022, 9:07 PM

Y by

(geometric)

This post has been edited 1 time. Last edited by PSS_73939133, Jan 27, 2022, 10:03 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a