Existence in number theory

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

Existence in number theory

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

97 posts

#1 h Nov 26, 2021, 2:22 PM

Y by

Prove that there are infinitely many integers can't be written as $\frac{p^a-p^b}{p^c-p^d}$ , with a,b,c,d are arbitrary integers and p is an arbitrary prime such that the fraction is an integer too.

This post has been edited 2 times. Last edited by shangyang, Nov 27, 2021, 4:02 AM

Z K Y

The post below has been deleted. Click to close.

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

3 posts

#2 h Nov 27, 2021, 1:17 AM

Y by

It seems that those integers which suits
$n\equiv -1(mod p)$ will help.

Z K Y

The post below has been deleted. Click to close.

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

97 posts

#3 h Nov 27, 2021, 3:06 AM

Y by

No because p can be changed arbitraryly, it's not fixed.

This post has been edited 2 times. Last edited by shangyang, Nov 27, 2021, 3:07 AM

Z K Y

The post below has been deleted. Click to close.

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

97 posts

#4 h Nov 27, 2021, 7:18 AM

Y by

Although I am the person who asked this question, I 've come up with this solution. Hope that anyone can verify it for me. Many thanks.
Firstly, we will find out when the fraction is an integer. We have
$\frac{p^a-p^b}{p^c-p^d}=\frac{p^b(p^{a-b}-1)}{p^d(p^{c-d}-1)}$ So we can infer that $b\geq d$ and from the lemma undermentioned, we conclude that $c-d\mid a-b$ .
Lemma. For $a\geq 2 \in \mathbb{Z}$ and $m,n$ are positive integers, we have
$\gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1$ .
Now we're good to go, there exists nonnegative integers $x,y,z$ such that
$\frac{p^a-p^b}{p^c-p^d}=p^x\cdot \frac{p^{yz}-1}{p^y-1}$ .
For the sake of clarity, for a prime $p$ ,denote a number $n$ to be $p$ -good if there doesn't exist nonnegative integers $x,y,z$ such that
$n=p^x\cdot \frac{p^{yz}-1}{p^y-1}$ .
Now it's easy to see that if this equation has integer root $(x,y,z)$ then either $p\mid n$ or $p\mid n-1$ .
It follows that $n$ is a $p$ -good number for all prime $p> n$ . (1)
We will prove that for sufficiently large $k$ , the number of the form $2^k\cdot 11$ will be $p$ -good for all $p< n$ , then from (1), we obtain the satisfied number. Indeed, consider the funtion $f(x,b)=\frac{x^b-1}{x-1},x,b\in\mathbb{Z}$ , then this funtion is strictly increasing with respect to $x$ and $b$ . So, for all $x\geq 3$ , we have
$f(x,b)=\frac{x^b-1}{x-1}\geq \frac{3^b-1}{3-1}$ . And now there exists $n_0$ sufficiently large such that, for all $b\geq n_0$ we have $f(x,b)=\frac{x^b-1}{x-1}\geq \frac{3^b-1}{3-1}>11b$ . Pick two prime of the form $11k+1$ , let's choose $23$ and $67$ then it's easy to see that, if we call $t=lcm(\varphi(23),\varphi(67))=66$ then $\gcd(t,10)=2$ . Choose $k$ sufficiently large enough such that $2^k>n_0$ , $k\equiv 0 \mod t$ and $k\equiv 2 \mod 10$ , since $\gcd(t,10)\mid 2-0$ thus this congruent equation has a root $k$ . By doing this, we have $23\cdot 67\mid 2^k\cdot 11-1$ , thus we have ensured that $n-1$ is not a prime number. We will prove that $n=2^k\cdot 11$ is the desired number. We observe that $11=\overline{1011}_2$ , so $n$ is a $2$ -good number. Consider the equation
$n=11^x\cdot \frac{11^{yz}-1}{11^y-1}$ Suppose this equation has integer root $(x,y,z)$ , since $v_{11}(n)=1$ , it follows that $x=1$ and $2^k= \frac{11^{yz}-1}{11^y-1}\equiv 1\mod 11$ but since $k\equiv 2\mod 10\Rightarrow 2^k\equiv 2^2\equiv 4\mod 11$ , a contradiction. So $2^k\cdot 11$ is a $11$ -good number. So far we've prove that $n$ is $p$ good for all $p\mid n$ , thus we remained to consider $p\mid n-1$ . Since $x=0$ , we have to consider the equation:
$2^k\cdot 11= \frac{p^{yz}-1}{p^y-1}$ .
Suppose this equation has root for $p\mid n-1$ , of course $p\neq 2$ , then $k=v_2(2^k\cdot 11)=v_2\left(\frac{p^{yz}-1}{p^y-1}\right)=v_2(z)$ . Thus $z\geq 2^k>n_0$ and $2^k\cdot 11=2^{v_2(z)}\cdot 11\leq 11z$ . Since $p^y\geq 3$ , we infer that
$\frac{p^{yz}-1}{p^y-1}\geq \frac{3^{z}-1}{3-1}>11z\geq 2^k\cdot 11$ , because $z>n_0$ which is a contradiction. So $n$ is a $p$ -good number for all $p\mid n-1$ . So $n$ is the desired number and it's easy to see that there are infinitely many ways to choose $k$ . Hence proved.

This post has been edited 1 time. Last edited by shangyang, Nov 27, 2021, 7:19 AM

Z K Y

The post below has been deleted. Click to close.

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

148 posts

#5 h Mar 21, 2025, 3:51 AM

Y by

R

shangyang wrote:

Prove that there are infinitely many integers can't be written as $\frac{p^a-p^b}{p^c-p^d}$ , with a,b,c,d are arbitrary integers and p is an arbitrary prime such that the fraction is an integer too.

Numbers with form $2^cP^d$ with $c\in\mathbb{N}, \nu_2(c)$ very big, arbitrary prime $P$ with form $8k+3$ and any odd number $d>1$ can’t express as the desire form
Is it true?

Attachments:

Z K Y

The post below has been deleted. Click to close.

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

148 posts

#6 h Mar 21, 2025, 4:09 AM

Y by

shangyang wrote:

Suppose this equation has root for $p\mid n-1$ , of course $p\neq 2$ , then $k=v_2(2^k\cdot 11)=v_2\left(\frac{p^{yz}-1}{p^y-1}\right)=v_2(z)$ . Thus $z\geq 2^k>n_0$ and $2^k\cdot 11=2^{v_2(z)}\cdot 11\leq 11z$ .

But if $2\nmid y,2|z$ , then $\nu_2\left(\frac{p^{yz}-1}{p^y-1}\right)=\nu_2(\frac{p^2-1}{2})+\nu_2(z)-\nu_2(p-1)=\nu_2(\frac{p+1}{2})+\nu_2(z)$
Then $z\ge 2^k$ may fail if $\nu_2(\frac{p+1}{2})$ is very big, how do you fix it?

This post has been edited 1 time. Last edited by shanelin-sigma, Mar 21, 2025, 4:10 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a