Euclid NT

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

Euclid NT

G H J

Reveal topic tags

2023 Fall TJ Proof TST

L

G H BBookmark kLocked kLocked NReply

Source: 2023 Fall TJ Proof TST, Problem 4

The post below has been deleted. Click to close.

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

1757 posts

Taco12

#1 h Oct 6, 2023, 12:50 AM • 2 Y

Y by megarnie, ItsBesi

Find all pairs of positive integers $(a,b)$ such that $a^2b-1 \mid ab^3-1.$
Calvin Wang

This post has been edited 1 time. Last edited by Taco12, Oct 6, 2023, 12:50 AM

Z K Y

The post below has been deleted. Click to close.

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

1924 posts

#2 h Oct 6, 2023, 1:42 AM

Y by

The original problem had way more conditions but apparently without the conditions was still solvable and rather interesting lol.

Doing sufficient Euclid yields
$a^2b-1\mid a^5-1,$ $a^2b-1\mid a^3-b,$ $a^2b-1\mid a-b^2.$
Caseworking on size for the second and third divisibilities yields $\boxed{(1,b)}$ , $\boxed{(b^2,b)}$ , and $\boxed{(a,a^3)}$ , which all work.

Z K Y

The post below has been deleted. Click to close.

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

1432 posts

#3 h Oct 6, 2023, 1:49 AM

Y by

I claim all answers are $(a,b)=(1,b), (b^2,b), (b,b^3)$ , where $b$ is arbitrary.

First, see that for $a=1$ , any $b$ works; so let $a>1$ . Next, $a^2b-1\le ab^3-1$ , so $b^2\ge a$ . We have $a^2b-1\mid ab^3-a^2b=ab(b^2-a)$ , so $a^2b-1\mid b^2-a$ . If $b^2=a$ , then any $b$ works, so let $b^2>a$ . Now, using $a^2b-1\mid a^3b-a$ , we find $a^2b-1 \mid b(a^3-b)$ , that is $a^2b-1\mid a^3-b$ .
Case 1. $b=a^3$ . In this case, clearly any $b$ works.
Case 2. $b>a^3$ . Then, $a^2b-1\mid b-a^3$ , so $b\ge a^3-1+a^2b\ge 4b$ as $a\ge 2$ , a contradiction.
Case 3. $b<a^3$ . Then, $a^2b-1\mid a^3-b$ , so $a^3\ge a^2b+b-1\ge a^2b$ , so $a\ge b$ . But then, using $a^2b-1\mid b^2-a$ we have $b^2\ge a+a^2b-1\ge a^2b\ge b^3$ , forcingn $b=1$ . For $b=1$ , $a^2-1\mid a-1$ , yielding $a=1$ .

This post has been edited 1 time. Last edited by grupyorum, Oct 6, 2023, 1:50 AM

Z K Y

The post below has been deleted. Click to close.

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

1556 posts

#4 h Oct 6, 2023, 2:18 AM • 2 Y

Y by vrondoS, MS_asdfgzxcvb

Note that $a^2b-1 \mid ab^3-1 \implies a^2b-1 \mid a^2b^3-a-(a^2b^3-b^2) \implies a^2b-1 \mid b^2-a \implies |b^2-a| \ge a^2b-1$
Also $a^2b-1 \mid ab^3-1 \implies a^2b-1 \mid a^4b^3-a^3 \implies a^2b-1 \mid a^3-b \implies |a^3-b| \ge a^2b-1$ .
Now if $a=1$ then all $b$ work so $(1,n)$ is a solution, also note if $b=1$ then $a=1$ (which is $(1,1)$ which we already have), now if $a,b \ge 2$ , then we have the following cases.
Case 1: $b \ge a^3$
Then here $b-a^3 \ge a^2b-1$ or $b=a^3$ , if the first one holds then $b-8 \ge b-a^3 \ge a^2b-1 \ge 4b-1$ contradiction!, hence another solution pair from this case is $(n,n^3)$
Case 2: $b<a^3$
Case 2.1: $a \ge b^2$
Then $a=b^2$ or $a-b^2 \ge a^2b-1$ hence $a-4 \ge a-b^2 \ge ba^2-1 \ge 2a^2-1$ contradiction! hence $a=b^2$ so $(n^2,n)$ is another solution.
Case 2.2: $b^2>a$
$a^3 \ge a^2b+b-1>a^2b$ hence $a \ge b+1$ hence $b^2-b-1 \ge b^2-a \ge a^2b-1 \ge b^3-2b^2+b-1>b^3-2b^2-b-1$ so $3b^2>b^3$ hence $b=2$ but then $4-a \ge 4a^2-1$ for all $a \ge 3$ which cant happen, so contradiction!.
Hence all the pairs are $(1,n), (n^2, n), (n, n^3)$ thus we are done

.

Z K Y

The post below has been deleted. Click to close.

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

DottedCaculator

7357 posts

DottedCaculator

#5 h Oct 6, 2023, 2:22 AM

Y by

Subtracting gives $a^2b-1\mid ab(b^2-a)$ so $a^2b-1\mid b^2-a$ . Therefore, either $a=b^2$ , which works, or $a^2b-1\leq b^2-a$ . We also have $a^2b-1\mid ab^3-1-(a^4b^2-1)=ab^2(b-a^3)$ , so either $b=a^3$ , which works, or $a^2b-1\leq a^3-b$ . This implies $b<a$ , contradicting the first inequality.

Z K Y

The post below has been deleted. Click to close.

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

4191 posts

#7 h Oct 7, 2023, 8:05 PM

Y by

The answer is $a=1$ and $a=b^2$ and $b=a^3.$ When $a=1$ , the statement is $b-1\mid b^3-1$ , which is true by difference of cubes factorization, and when $a=b^2$ the two sides are equal. When $b=a^3$ , the statement is $a^5-1\mid a^{10}-1$ which is true by difference of squares.

From now on, assume $a\geq 2$ since we already know that $a=1$ always works.

Rewrite the condition as $ab^3-1\equiv 0\pmod{a^2b-1}.$ Since $a^2b-1$ is relatively prime to $a$ , we will multiply this by $a$ to get $a^2b^3-a\equiv 0\pmod{a^2b-1}.$ We subtract $a^2b^3-b^2$ from the left side (since that is $b^2$ times the modulus), to get $b^2\equiv a\pmod{a^2b-1}.$ Now, let $b^2=a+k(a^2b-1)$ for some integer $k$ . If $k=0$ , then we have $a=b^2$ which we know works, so from now on assume $k\neq 0.$ Clearly, $k$ cannot be negative either, as $a^2b-1\geq a^2-1>a$ since we are assuming $a\geq 2.$ Thus, $k$ is a positive integer.

Now, rearrange this as a quadratic in $b$ to get $b^2+(-a^2k)b+k-a=0.$ Since $b$ must be an integer, we have that the discriminant must be a perfect square. Thus, $a^4k^2+4(a-k)$ must be a square.

Claim 1: $(a^2k-1)^2<a^4k^2+4(a-k).$ Expanding this out gives $-2a^2k+1<4a-4k$ $4k+1<4a+2a^2k.$ This is clearly true, since we are assuming $a\geq 2$ so $2a^2k+4a\geq 8k+8>4k+1.$
Claim 2: $(a^2k+1)^2>a^4k^2+4(a-k).$ Expanding this out gives $2a^2k+1>4a-4k$ $2a^2k+4k+1>4a.$ Again, this is clearly true since we are assuming $a\geq 2$ so $2a^2k+4k+1>2a^2k\geq 2a^2\geq 4a.$
Thus, the only way for it to be a perfect square is if $a^4k^2+4(a-k)=(a^2k)^2$ $a=k.$
However, if we plug it back into $b^2+(-a^2k)b+k-a=0,$ this just becomes $b^2-a^3b=0,$ which has the solution $b=a^3,$ hence done.

Z K Y

The post below has been deleted. Click to close.

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

799 posts

#8 h Mar 11, 2024, 7:37 PM

Y by

Does $0 \mid 0$ ? Probably doesn't, so we exclude $(1,1)$ in the solution set.

Note the LHS must be less than or equal to the RHS, so $a \leq b^2$ . Euclid also tells us
$a^2b-1 \mid (ab^3-1)-(a^2b-1) = ab(b^2-a).$

$\min(a,b)=1$ : Our solutions are $\boxed{(1,k)}$ .
Otherwise, $a^2b-1 \mid b^2-a$ . If $b \leq a^2$ , the RHS must be 0, we get the solution $\boxed{(k^2,k)}$ .
Otherwise, $a^2b-1 \mid a(a^2b-1) - (b^2-a) = b(b-a^3)$ , and as $|b-a^3| < |a^2b-1|$ , we require $\boxed{(k,k^2)}$ . $\blacksquare$

This post has been edited 1 time. Last edited by shendrew7, Mar 11, 2024, 7:59 PM

Z K Y

The post below has been deleted. Click to close.

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

3789 posts

vsamc

#9 h Mar 11, 2024, 8:15 PM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

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

4243 posts

#10 h Aug 9, 2024, 12:02 AM

Y by

Clearly, $a=1$ and $a=b^2$ are both solutions. When $a>b^2$ , the LHS is greater than the RHS, so let $1<a<b^2$ . Note that $\gcd(a^2b-1, ab^3-1)=\gcd(a^2b-1, b^2-a)$ . Clearly, when $a\ge \sqrt{b}$ , $b^2-a<a^2b-1$ . Therefore, $1<a<\sqrt{b}$ so $1<a^2<b$ .

Let $b=a^2+k_2$ for $k_2>0$ . Then, $\gcd(a^2b-1, b^2-a)=\gcd(a^4+k_2a^2-1, a^4+2k_2a^2+k_2^2-a)=\gcd(a^4+k_2a^2-1, k_2a^2+k_2^2-a+1).$
Clearly, $k_2a^2+k_2^2-a+1>0$ , so $k_2a^2+k_2^2-a+1\ge a^4+k_2a^2-1$ so $k_2^2+2\ge a^4+a$ . When $k_2=a^2$ , $a=2$ so $(2, 8)$ is a solution. Otherwise, $k_2>a^2$ . Let $k_2=a^2+k_3$ for $k_3>0$ . Then, $\gcd(a^4+k_2a^2-1, k_2^2+2-a^4-a)=\gcd(2a^4+k_3a^2-1,2a^2k_3+k_3^2-a+2).$
Clearly, $2a^2k_3+k_3^2-a+2>0$ , so $2a^2k_3+k_3^2-a+2\ge 2a^4+k_3a^2-1$ , so $a^2k_3+k_3^2+3\ge 2a^4+a$ . When $k_3=a^2$ , we get $a=3$ , so $(3, 27)$ is a solution. Otherwise, $k_3>a^2$ . Let $k_3=a^2+k_4$ for $k_4>0$ . Then, $\gcd(2a^4+k_3a^2-1,a^2k_3+k_3^2+3-2a^4-a)=\gcd(3a^4+k_4a^2-1, 3k_4a^2+k_4^2-a+3).$
Clearly, $3k_4a^2+k_4^2-a+3>0$ so $3k_4a^2+k_4^2-a+3\ge 3a^4+k_4a^2-1$ so we get $2k_4a^2+k_4^2+4\ge 3a^4+a$ . When $k_4=a^2$ , we get $a=4$ so $(4, 64)$ is a solution. Otherwise, $k_4>a^2$ .

It is easy to see that by induction, $k_n=a^2+k_{n+1}$ implies that $((n+1), (n+1)^3)$ is a solution and otherwise $k_{n+1}=a^2+k_{n+2}$ . As $b$ must be finite, there are no solutions other than $b=a^3$ in this case.

Therefore, the solutions are $a=1$ , $a=b^2$ , and $b=a^3$ .

Z K Y

The post below has been deleted. Click to close.

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

23 posts

#11 h Jan 26, 2025, 6:55 AM • 1 Y

Y by MS_asdfgzxcvb

Let $n=a^2b-1,$ for simplicity, and note that $(a,n)=(b,n)=1.$

$1\equiv ab^3 \equiv a\times (a^{-2})^3 \equiv a^5 \pmod n$ So $b$ is just the inverse of $a^2$ modulo $n$ which is $a^3.$
Hence, $b\equiv a^3 \pmod n$ and $b^2\equiv a \pmod n.$

$\begin{align*} n &\mid b-a^3 \\ n &\mid b^2-a \\ n &\mid a^5-1 \end{align*}$ Now, it is just a size argument and the answer is $(1,n),(n^2,n)$ and $(n,n^3).$

This post has been edited 2 times. Last edited by math004, Jan 26, 2025, 6:56 AM
Reason: .

Z K Y

The post below has been deleted. Click to close.

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

243 posts

pie854

#12 h Feb 11, 2025, 9:00 AM

Y by

Notice that $(1,x)$ works. Assume $a, b>1$ . Then $a^2b-1 \leq ab^3-1$ i.e. $b^2\geq a$ . The pair $(x^2.x)$ works so let's assume $b^2>a$ . Note that $a^2b-1 \mid a(ab^3-1)-b^2(a^2b-1)=b^2-a.$ This implies $b^2+1>a^2b+a$ which implies $b>a^2$ . Now $a^2b-1 \mid b(a^2b-1) - a^2(b^2-a)=a^3-b.$ If $a^3-b>0$ then, $a^3-b\geq a^2b-1$ i.e. $a^3+1 \geq b(a^2+1)>a^2(a^2+1)$ , a contradiction. If $a^3-b<0$ then $b-a^3 \geq ab^2-1$ which is clearly absurd. Hence $a^3=b$ and we can check that $(x,x^3)$ works.

Z K Y

The post below has been deleted. Click to close.

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

1748 posts

OronSH

#13 h Feb 27, 2025, 8:37 PM

Y by

First $a^2b-1\mid -a(ab^3-1)+b^2(a^2b-1)=a-b^2\implies a^2b-1\mid a^2(a-b^2)+b(a^2b-1)=a^3-b$ . Now $a\ne 1\implies a^2b-1>b-a^3$ so either $b=a^3$ or $a^3-b\ge a^2b-1\implies a^3-a^2b-b+a\ge 0\implies (a^2+1)(a-b)\ge 0\implies a\ge b$ . Now from $a^2b-1\mid a-b^2$ either $a=b^2$ or $a^2b-1\ge b^2-1>b^2-a\ge a^2b-1$ or $a^2b-1>a-1\ge a-b^2\ge a^2b-1$ , contradiction. This gives our solutions $(1,t),(t,t^3),(t^2,t)$ which clearly work.

Z K Y

The post below has been deleted. Click to close.

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

667 posts

#14 h Apr 25, 2025, 4:12 PM

Y by

Note that the LHS is relatively prime to $a,$ so we multiply the RHS by $a$ . This tells us that $a^2b - 1 \mid a^2b^3 - a \implies a^2b - 1 \mid b^2 - a.$ Multiplying by $a^2,$ it gives $a^2b - 1 \mid b - a^3.$ Now we casework on $b^2$ and $a.$

If $a = b^2,$ this clearly works.

If $a > b^2,$ we have that $a - b^2 < a^2b - 1,$ however, $a - b^2 > 0,$ which gives no solutions.

If $a < b^2,$ we do casework on $a^3 < b$ or $a^3 = b$ . Continue by multiplying by $a^2$ , and subtracting by the LHS. Clearly, the RHS must be non-negative. Thus, $1 - a^5 = 0 \implies a = 1.$

Thus, the solution set is $(1, k), (k, k^3), (k^2, k)$ where $k > 1.$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a