S 5

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

S 5

G H J

Reveal topic tags

greatest common divisor

Miscellaneous Problems

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:26 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

Suppose that both $x^{3}-x$ and $x^{4}-x$ are integers for some real number $x$ . Show that $x$ is an integer.

Z K Y

The post below has been deleted. Click to close.

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

337 posts

#2 h Oct 17, 2007, 4:20 PM • 3 Y

Y by Adventure10, Mango247, and 1 other user

Suppose $x\neq0$ .
We have $\dfrac{x^4-x}{x^3-x}\in\mathbb{Q}$ , from where $\dfrac{x^2}{x+1}=q\in\mathbb{Q}$ . So $x^2=xq+q$ . Then $A=x^3-x=x(xq+q)+q=x^2q+xq+q=(xq+q)q+xq+q$ . Since $A=x^3-x\in\mathbb{Z}$ , we have that $2xq+q^2+q\in\mathbb{Z}$ , from where $x$ is a rational number. Now, if $x=\dfrac uv$ , with $\gcd(u,v)=1$ . Suppose $x\notin\mathbb{Z}$ . Then there exists a prime number $p$ dividing $v$ . To have $x^3-x\in\mathbb{Z}$ , we need $p^3|u^3-uv^2$ , which is impossible because $(p,u)=1$ but $p|v$ .

Z K Y

The post below has been deleted. Click to close.

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

6 posts

azo

#3 h Feb 17, 2009, 10:00 PM • 4 Y

Y by Adventure10, Mango247, Mango247, Mango247

I'm not sure wheater the proof is correct. How did you concluded the following equality?

$A = x^3 - x = x(xq+q) + q$

Z K Y

The post below has been deleted. Click to close.

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

1312 posts

#4 h Feb 17, 2009, 10:34 PM • 2 Y

Y by Adventure10, Mango247

azo wrote:

I'm not sure wheater the proof is correct. How did you concluded the following equality?

$A = x^3 - x = x(xq + q) + q$

Since $xq + q = x^2$ we have $x^3 - x = x(xq + q) + q = x^3 + q \iff q = - x$ which is clearly wrong, so I think there is a mistake.

Z K Y

The post below has been deleted. Click to close.

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

345 posts

#5 h Feb 17, 2009, 11:28 PM • 2 Y

Y by Math1331Math, Adventure10

We can solve it with minimal polynomial - $x$ is clearly an algebraic integer. Let $p$ be its minimal polynomial - the monic polynomial with integer coefficients of smallest degree such that $x$ is its zero (its existence is easy to prove, and it divides any other polynomial with these properties (except for the minimality)). By the given data, it is of degree at most $3$ . We want to show that it is of degree $1$ .
Let $a_1 = x^3 - x, a_2 = x^4 - x$ , and define $p_1(t) = t^3 - t - a_1, p_2(t) = t^4 - t - a_2$ .
If $a_1 = 0$ or $a_2 = 0$ , we get that $x = 0$ or $x = \pm 1$ and we're done. Otherwise-
Notice that $p_2(t) - tp_1(t) = t^2 + t(a_1 - 1) - a_2$ . This polynomial must be divisible by the minimal polynomial. If, for contradiction's sake, we assume that its degree is $2$ , then it is exactly $t^2 + t(a_1 - 1) - a_2$ , and it follows that $t^2 + t(a_1 - 1) - a_2|t^3 - t - a_1, t^4 - t - a_2$ .
Putting $t = 0,1$ yields $a_1 - a_2, a_2|(a_1,a_2)$ , and it follows that $a_2|a_1$ and then $a_1 - a_2 = \pm a_2 \implies a_1 = 2a_2$ .
Now we'll calculate the gcd:
$(x^3 - x - a_1,x^4 - x - a_2) = (x^2 + x(a_1 - 1) - a_2,x^3 - x - 2a_2) = (x^2 + x(a_1 - 1) - a_2,x^2(1 - a_1) + x(a_2 - 1) - 2a_2)$
and unless $(1 - a_1,a_2 - 1, - 2a_2) = C(1,a_1 - 1, - a_2)$ for some constant $C$ , the gcd is of degree 1 and we're done. But $C = 2$ (because of the coefficient of $x^0$ ) so if follows that $a_1 = - 1,a_2 = - 3$ . But it contradicts $a_1 = 2a_2$ , so the gcd is indeed linear.

Z K Y

The post below has been deleted. Click to close.

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

337 posts

#6 h Feb 18, 2009, 12:23 AM • 2 Y

Y by Adventure10, Mango247

azo wrote:

I'm not sure wheater the proof is correct. How did you concluded the following equality?

$A = x^3 - x = x(xq + q) + q$

Thanks for pointing out. My proof is certainly wrong. No idea how could I have concluded that

Anyway, let me try once more and hope I don't mess it up again

So $x^3 - x = x\cdot x^2 - x = x(xq + q) - x$ $= x^2q + qx - x = (xq + q)q + qx - x = (q^2 + q - 1)x + q^2$ , yielding $x$ is rational and I think we can continue in the same way.

This seems way too simple, so sorry if I am wrong again...

Z K Y

The post below has been deleted. Click to close.

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

1312 posts

#7 h Feb 18, 2009, 4:30 PM • 2 Y

Y by Adventure10, Mango247

freemind wrote:

azo wrote:

I'm not sure wheater the proof is correct. How did you concluded the following equality?

$A = x^3 - x = x(xq + q) + q$

Thanks for pointing out. My proof is certainly wrong. No idea how could I have concluded that

Anyway, let me try once more and hope I don't mess it up again

So $x^3 - x = x\cdot x^2 - x = x(xq + q) - x$ $= x^2q + qx - x = (xq + q)q + qx - x = (q^2 + q - 1)x + q^2$ , yielding $x$ is rational and I think we can continue in the same way.

This seems way too simple, so sorry if I am wrong again...

Your last solution is good!

Quote:

Notice that $p_2(t) - tp_1(t) = t^2 + t(a_1 - 1) - a_2$ . This polynomial must be divisible by the minimal polynomial.

Why is that?

Z K Y

The post below has been deleted. Click to close.

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

345 posts

#8 h Feb 18, 2009, 5:30 PM • 2 Y

Y by Adventure10, Mango247

The minimal polynomial divides $p_2$ and $p_1$ , thus it divides any linear combination of them (and also their GCD).
Proof that the minimal polynomial of $a$ , $p$ , divides any polynomial $q$ in $Z[X]$ that $a$ is its zero:
$g(t)=(p,q)$ is of degree less than\equal to $p$ 's degree, and $g(a)=0$ (by Bizut Lemma: g is a linear combination of $p$ and $q$ . put x=a).
Thus, from the minimality of $p$ , $g$ and $p$ are the same up to a constant (if they are of the same degree but not the same up to a constant, you can find a linear combination of them of degree less than their degree, and it is 0 at $x=a$ ), which means that $p|q$ , QED.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a