N 17

Art of Problem Solving

AoPS Online

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

N 17

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.

3615 posts

Peter

#1 h May 25, 2007, 12:25 AM • 3 Y

Y by Adventure10 and 2 other users

Suppose that $a$ and $b$ are distinct real numbers such that $a-b, \; a^{2}-b^{2}, \; \cdots, \; a^{k}-b^{k}, \; \cdots$ are all integers. Show that $a$ and $b$ are integers.

Z K Y

The post below has been deleted. Click to close.

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

232 posts

edriv

#2 h May 25, 2007, 12:25 AM • 2 Y

Y by Adventure10 and 1 other user

First, we prove that a,b are rational numbers.
$a-b \in \mathbb{Q}$
$a+b = \frac{a^2-b^2}{a-b} \in \mathbb{Q}$
$a = \frac{(a+b)+(a-b)}2 \in \mathbb{Q}$
$b = \frac{(a+b)-(a-b)}2 \in \mathbb{Q}$

Then we can find three integers a',b',n such that:
$a = \frac{a'}n$
$b = \frac{b'}n$
$d \mid a' \land d \mid b' \land d \mid n \Rightarrow |d| = 1$
The hypotesis translates to $n^k \mid a'^k - b'^k \quad \forall k \in \mathbb{N}$ .
Now, $n \mid a'-b'$ and we can suppose $(a',n) = 1$ . Therefore $(b',n) = 1$ .

Let d be the integer such that $n^d \mid \mid a'-b'$ . First, we suppose d>1.
We have $n^{d+1} \mid a'^{d+1} - b'^{d+1} = (a'-b')(a'^d + \ldots + b'^d)$ . We get $n \mid (a'^d + \ldots + b'^d)$ , but $\gcd(a'-b', a'^d + \ldots + b'^d) \mid n$ , therefore $n \mid \mid (a'^d + \ldots + b'^d)$ and $n^{d+1} \mid \mid a'^{d+1} - b'^{d+1}$ . (in this step we must remember that d>1).

Now we consider 2(d+1). We know that $n^{2d+2} \mid a'^{2d+2} - b'^{2d+2} = (a'^{d+1} + b'^{d+1})(a'^{d+1}-b'^{d+1})$ . But $n^{d+1} \mid \mid a'^{d+1} - b'^{d+1}$ , then $n^{d+1} \mid a'^{d+1} + b'^{d+1}$ and $n^{d+1} \mid (a'^{d+1} + b'^{d+1}) + (a'^{d+1} - b'^{d+1}) = 2a'^{d+1}$ . But $(a',n) = 1$ , then finally $n^{d+1} \mid 2$ .
But therefore, n=1 and a,b are integers.

If $n \mid \mid a'-b'$ , then $n^2 \mid (a'+b')(a'-b')$ and $n \mid a'+b'$ and $n \mid 2a'$ , as before. Then n=2 and a',b' are odd integers such that a'-b' is a multiple of 2 but not of 4. Let us take d such that $2^d \mid \mid a'+b'$ . Let us take a positive integer k such that $2^k - k > d$ (this obviously exists).
But then $2^{2^k} \mid a'^{2^k} - b'^{2^k} = (a'^{2^{k-1}} - b'^{2^{k-1}}) \cdots (a'^2+b'^2)(a'+b')(a'-b')$ . We must find $2^k$ factors 2 in this product. But if x,y are odd integers, $2 \mid \mid x^2+y^2$ . And $2 \mid \mid a'-b'$ by hypotesis, and $2^d \mid \mid a'+b'$ by hypotesis. Therefore we find exactly $d + k$ factors 2 in this product, which is too low.

I hope it is correct!

I hope it is correct!

Z K Y

The post below has been deleted. Click to close.

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

345 posts

#3 h Oct 19, 2008, 5:33 PM • 2 Y

Y by Adventure10, Mango247

Lets say we showed that a,b are rational (like edriv did). Let: $a = \frac {x}{y}, b = \frac {s}{t}, (s,t) = (x,y) = 1$

$a^n - b^n \in Z, n \in N \leftrightarrow (yt)^n|(xt)^n - (ys)^n$ . If we show that $yt|xt, ys$ , we get: $y|x$ , $t|s$ , or: $a,b$ are integers. It follows from the following lemma:

Lemma: If $a^n|b^n - c^n$ for all $n \in N$ , where $a$ , $b \neq c$ are integers, then: $a|b,c$ .
Proof: Let p be a prime divisor of a, $g = gcd(b,c)$ , ( $b' = b/g, c = c'/g$ ). We have, by "Lifting the Exponent" lemma:
$ord_p(a^n) \le ord_p(b^n - c^n) =$
$ord_p(g^n) + ord_p(b'^n - c'^n) =$
$ord_p(g^n) + ord_p(b' - c') + ord_p(n) =$
$ord_p(n(b - c)g^{n - 1})$
or (in the case p=2):
$ord_p(a^n) \le ord_p(b^n - c^n) = ord_p(g^{n - 2}(b^2 - c^2)n/2)$ .

We can put that together in the following way - $ord_p(a^n) \le ord_p(g^{n - 1}(b^2 - c^2)n)$ .

It implies that: $a^n | g^{n}(b^2 - c^2)n$ for all n>1. Let $gcd(a,g) = g'$ . We have: $(\frac {a}{g'})^n|(b^2 - c^2)n$ , which implies that:
$|(\frac {a}{g'})^n| \le |b^2 - c^2|n$ for all n>1. It can't happen for large n unless $b^2 - c^2 = 0$ or $a = \pm g'$ .

First case - $b^2 = c^2$ . It means that $b = - c$ , or: $a^{2n - 1}|2b^{2n - 1}$ for all n, which gives $a|b$ , and then also $a|c$ .
Second case - $a = \pm g'$ , or: $a|b,c$ .

Q.E.D.

"Lifting the Exponent": If p is an odd prime, and a,b are integers, and: $p|a - b, (a,b,p) = 1$ , we have: $ord_p(a^n - n^n) = ord_p(n(a - b))$
If p=2, $p|a - b, (a,b,p) = 1$ , we have: $ord_p(a^n - n^n) = ord_p(n(a^2 - b^2)/2)$

I have dropped out some minor details, ask a question or point an error if you find one.

Z K Y

The post below has been deleted. Click to close.

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

114 posts

#4 h Dec 7, 2008, 12:28 PM • 2 Y

Y by Adventure10, Mango247

Sorry for spam.But what "GML" mean ?

Z K Y

The post below has been deleted. Click to close.

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

1647 posts

#5 h Dec 7, 2008, 4:33 PM • 1 Y

Y by Adventure10

I assume it's George T. Gilbert, Mark I. Krusemeyer, Loren C. Larson, The Wohascum County Problem Book, MAA.

Z K Y

The post below has been deleted. Click to close.

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

520 posts

#6 h Dec 7, 2008, 5:45 PM • 2 Y

Y by Adventure10, Mango247

Here is a proof a little bit different from edriv. It is the same up to
$n|a'-b'$ , $(n,a')=(n,b')=1$ .

We can also assume $n>0$ wlog.

Let $a'=An+b'$ , we know
$n^k|a'^k-b'^k=\sum_{i=2}^k c_i(An)^ib'^{k-i}+kAnb'^{k-1}$ , where $c_i$ is binomial coefficients.
We can always find big $k$ with $(k,n)=1$ .
Note the first term on RHS is multiple of $(An)^2$ . So we have $n^2|kAnb'^{k-1}$ , or $n|A$ .
Then the first term on RHS is multiple of $(An)^2$ , or $n^4$ . So we have $n^4|kAnb'^{k-1}$ , or $n^3|A$ .
Then the first term on RHS is multiple of $(An)^2$ , or $n^8$ . So we have $n^8|kAnb'^{k-1}$ , or $n^7|A$ .
....
We have $n^m|A$ for any big integer $m$ , $A$ being nonzero finite number implies $n=1$ . Hence $a=a'$ and $b=b'$

Z K Y

The post below has been deleted. Click to close.

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

548 posts

#7 h Dec 15, 2021, 2:04 PM

Y by

$a = \frac {x}{z}, b = \frac {y}{z}, (x,y,z) = 1$
$p|z$
$p^n|x^n-y^n$ and $p|x-y$
by $LTE lemma$
$n \le v_p(x^n-y^n)=v_p(x-y)+v_p(n)$
$n=p^k$
$p^k-k \le v_p(x-y)$
contradiction

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a