quadratics
algebra
polynomial
special factorizations
difference of squares

[quote="7h3.D3m0n.117"]ahh its been a while since ive remembered how to do this

is there a simple way (no guess and check ways)

to factor

$3x^{2}+x-4$?

i used to remember an easy way but now i forgot  :huh:[/quote]

[hide]Well, first of all, since 3 is prime, you know it's of the form
$(3x+a)(x+b)$
Now you want to find $a$ and $b$ such that
$3b+a=1$
$ab=-4$
Then you would kind of guess and check from there. To the best of my knowledge, there really isn't a way to factor without some degree of guess and check.[/hide]

I think completing square could be a good way to approach this quesiton, but it does take a while...

But I think the answer is quite obvious for this one, it can be factorised to (3x+4)(x-1).

I hope this can help! :P

thanks!

yeah  but my father had a way i just don't remember it

(i don't dare ask him again because he'd kill me for forgetting such an important thing)

completing the square only works if it is set to 0...unless ur talking about something else?

[quote="7h3.D3m0n.117"]
completing the square only works if it is set to 0...unless ur talking about something else?[/quote]

Completing square should work absolutely fine if the quadratic polynomial can be factorised.

After completing the square, we will either get $(x+a)^{2}+b$ or $(x+a)^{2}-b$. After completing the square, if we obtain $(x+a)^{2}+b$, then the quadratic polynomial cannot be factorised; if we obtain $(x+a)^{2}-b$, then we can further factorise it with the "difference of squares" (let b be $c^{2}$.

I hope it does make sence! :P

here's another way to do it, its similar to the normal way but some ppl find it better..

$3x^{2}+x-4=\frac{(3x+a)(3x+b)}{3}$ so that $ab=-12$ and $a+b=1$ you quickly see $4$ and $-3$ as your wanted solution so

$\frac{(3x+4)(3x-3)}{3}=(3x+4)(x-1)$

ok but what is up with the 3 in the denominator?

umm its there because the numerator has an extra factor of $3$ so in general $y=ax^{2}+bx+c$ you have

$y=\frac{(a+k)(a+l)}{a}$ where $kl=c$ and $k+l=b$

ah yes! thanks for all the great replies ive found all of them helpful (certainly more so than my math teacher)

Or you could use the quadratic formula, find the roots, and factor it with the right 0s.

Nice solution MathTex  :lol:

There are a lot of ways to approach such kind of problem.

[b][size=150]1st solution:[/size][/b]

The main idea is the following:

Try to find the Discriminant of the equation . (Consider the following equation: $P(x) = ax^{2}+bx+c$) If it is positive (therefore it has two unequal real roots) we factorize by the use of the following type: $P(x) = a(x-x_{1})(x-x_{2})$ where $x_{1}$, $x_{2}$ are the real roots of the equation. So for the given equation we have:

$3x^{2}-x-4=0$

$D=(-1)^{2}-4\cdot3\cdot(-4)=1+48=49$

$x_{1,2}=\frac{-b\pm\sqrt{D}}{2a}=\frac{1\pm\sqrt{49}}{2\cdot3}=\frac{1\pm7}{6}$

$x_{1}=\frac{1+7}{6}=\frac{4}{3}$

$x_{2}=\frac{1-7}{6}=-1$

So the equation can be written:

$P(x) = 3\left(x-\frac{4}{3}\right)(x+1)$

$\hline$

[b][size=150]2nd solution[/size][/b]

[color=blue][u][b]Theorem[/b][/u]: Let the polynomial equation $a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots+a_{1}x+a_{0}=0$ such that $a, a_{n-1}, \ldots, a_{0}\in\mathbf{Z}$. If the integer $\rho$ is a root of the equation, then $a_{0}$ is a multiplier of $\rho$. [/color]

The possible divisors of $a_{0}$, in the specific occasion $-4$, are $\pm1, \pm2, \pm4$. By Horner's method we see that $-1$ is a root of the polynomial. By Horner's method again, we find that $P(x)=3(x+1)\left(x-\frac{4}{3}\right)$.

Last but not least, Horner's method is [u]very[/u] useful in factorization, if we have to deal with >=cubic equations.

To enhance on Horner's method visit:

http://mathworld.wolfram.com/HornersMethod.html

$\hline$

[size=150][b]PostScript[/b][/size]:

[u]Question[/u]:[i]Yes, but what can we do if the discriminant ($D$) equals to 0?[/i]

[u]Answer[/u]: If the equation has the following form: $P(x)=ax^{2}+bx+c$, make use of the following type:

$P(x)=a\left(x+\frac{b}{2a}\right)^{2}$


Hey peoples, I have this problem on the book I'm currently studying but they do not show the solution, do you think you can help me, please?

Prove there is only one combination of three positive integers (larger than 1) x,y,z which fulfil xy+1=0 (mod z), yz+1=0 (mod x), zx+1=0 (mod y).

Thanks!!!

Thanks Kunny!
Sorry, but I don't quite get what xy+yz+zx+1=0 (mod xyz) has to do with the question?

Please let me know...

Again, thanks very much!!

Is it anything to do with

xy+yz+zx=-1 (mod x) (mod y) (mod z) ??

That's equivalent to kunny's deduction surely....

Do you have a combination that works yet?

I have [hide]$(x,y,z) = (2,3,7)$, just because the first primes I tried were 2 and 3.[/hide] I don't have a proof that this is a unique solution though...

[quote="kunny"]Let $xy+1=pz,\ yz+1=qx,\ zx+1=ry$ such that $p,q,r$ are positive integers. We have
$(xy+1)(yz+1)(zx+1)=pqrxyz$
$\Longleftrightarrow 1+xy+yz+zx+xyz(x+y+z)+(xyz)^2=pqrxyz.$
Thus $xy+yz+zx+1$ should be devided by $xyz.$[/quote]

We can set $\frac{xy+yz+zx+1}{xyz}=N\ (N: postive\ integer)\ \cdots (*)$ Without Loss of Generality $2\leq x\leq y\leq z.$

Rewrite $N=\frac{1}{z}+\frac{1}{x}+\frac{1}{y}+\frac{1}{xyz}\leq \frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\frac{1}{8}=\frac{13}{8},$ yielding $N=1.$ Plugg this into $(*)$ and rewrite

$x=\frac{xy+yz+zx+1}{yz}=\frac{x}{z}+1+\frac{x}{y}+\frac{1}{yz}\leq 1+1+1+\frac{1}{2\cdot 2}=3.25,$

yielding $x=2,3.$ Then plugg these into $(*),$ you are to examine for $x=2,3$

WOW! Thanks very much kunny!
That was a help!!

Thanks!!

Fang


Let $ a$ and $ b$ be real numbers and let \[ f(x) \equal{} a \sin x \plus{} b \sqrt[3]{x} \plus{} 4.\] If \[ f(\log \log_{3} 10) \equal{} 5,\] what is the value of $ f(\log \log 3)$?

Note that $ f(x)\minus{}4$ is an odd function;
$ f(x)\minus{}4\equal{} a \sin x \plus{} b \sqrt[3]{x} \equal{} \minus{}(f(\minus{}x)\minus{}4)$

Also note that

$ \log\log_{3}10 \equal{} \log\frac{\log10}{\log3}\equal{}\log\log10\minus{}\log\log3\equal{}\minus{}(\log\log3\minus{}\log\log10) \equal{} \minus{}(\log\frac{\log3}{\log10})\equal{}\minus{}(\log\log{3})$

Thus, $ f(\log\log_{3}10)\minus{}4 \equal{} 1 \equal{} \minus{}(f(\log\log3)\minus{}4)\equal{}\minus{}f(\log\log3)\plus{}4$, and

$ f(\log\log3) \equal{} 3$


Person S and person P are given the sum and product, respectively, of two positive integers between $2$ and $99$ inclusive. Then they have the following conversation:

S: You don't know the two numbers.
P: I do now.
S: I also know now.

What were the two numbers?

i do not remember where and when i saw as exercices but the conversation wasn't verry schirt as u give in the problem :?:  :huh:

[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=1655602545&t=45703[/url]
[url]http://www.qbyte.org/puzzles/p003s.html[/url]

Those links should help.

And see [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=155023]here[/url] for a greater challenge.   :rotfl:


Let $ ABCD$ is a quadrilateral, let $ M$ is midpoint of $ AD$ and $ N$ is midpoint of $ BC$. Let $ CM$ meet $ DN$ at $ E$, $ BM$ meet $ AN$ at $ F$.

Prove that: $ \frac {AF}{NF} \plus{} \frac {BF}{MF} \plus{} \frac {CE}{ME} \plus{} \frac {DE}{NE} \ge 4$

Denote $ S_{ABC}\equal{}S_D, S_{BCD}\equal{}S_A, S_{CDA}\equal{}S_B, S_{DAB}\equal{}S_C$. Hence $ \frac{AF}{NF}\equal{}\frac{S_{AMB}}{S_{BNM}}\equal{}\frac{\frac{1}{2}S_C}{\frac{1}{2}S_{BCM}}\equal{}\frac{2S_C}{S_A\plus{}S_D}$. Analogically $ \frac{BF}{MF}\equal{}\frac{2S_D}{S_C\plus{}S_B}$, $ \frac{CE}{ME}\equal{}\frac{2S_A}{S_C\plus{}S_B}$, $ \frac{DE}{NE}\equal{}\frac{2S_B}{S_A\plus{}S_D}.$ Hence $ \frac {AF}{NF} \plus{} \frac {BF}{MF} \plus{} \frac {CE}{ME} \plus{} \frac {DE}{NE} \ge 4 \Leftrightarrow$ $ \frac{S_A\plus{}S_D}{S_B\plus{}S_C}\plus{}\frac{S_B\plus{}S_C}{S_A\plus{}S_D}\geq 2$ which is true :)

Thank [i][u][b]Flakky[/b][/u][/i]. It's nice solution. I can prove this problem but my solution is very long.


arithmetic sequence
algebra unsolved
algebra

If an aritmetic progression contains a square, then it contains infinite many squares.

Prove it..  :(  I don`t know how  :blush:

I'm not sure what you mean, but it looks hard to prove since:

${\{1-n;n\in Z^{+}\}}$ is an arithmetic progression containing just two squares.

http://www.mathlinks.ro/Forum/viewtopic.php?t=8091

  darij

Does progression mean that it's increasing or what?


geometry
combinatorics unsolved
combinatorics

There are seven dots on the board. In which condition of positions of dots, satisfy following stuffs.
 1. Cover the board with three convex area.(It can be any shape that is convex)
 2. Areas can meet, and it divides board by its border...(I don't know how to explain the case... idea of the picture is from ben diagram) It makes seven closed area. (I am sorry about my grammar mistake.)
 3. Each dots are included in each closed areas.

I do not understand a single word... :wink:

Pierre.


Let $ a>0 ,\; b\in {\mathbb R} $ and $ X_0,Y_0,Z_0 $ real numbers such that $ X_0\le Y_0\le Z_0 .$ If  $\left(X_n\right)_{n=0}^{\infty}\; , \left(Y_n\right)_{n=0}^{\infty}\; , \left(Z_n\right)_{n=0}^{\infty}\; , $ are real sequences such that
\[ \begin{array}{lcl}
X_{n+1} &\le & aX_n+b  \\
Y_{n+1} &= & aY_n+b  \\
Z_{n+1} &\ge & aZ_n+b  \\
\end{array}\; ,\; \forall n\in {\mathbb N},
\]
prove [b](without using induction)[/b] that   $\displaystyle X_n\le \displaystyle Y_n\le \displaystyle Z_n\; ,\; \forall n\in {\mathbb N}. $ Moreover, show that $\displaystyle Y_n=\left\{\begin{array}{lcl}
 \displaystyle Y_0+nb   &,& a=1\\  \displaystyle Y_0a^n+b\frac{a^n-1}{a-1} & , &  a\ne 1
\end{array}\right.\; . $

[quote="flip2004"]
prove [b](without using induction)[/b][/quote]

That is the kind of condition I never liked ...   :(  If one doesn't want that students use induction, just do not give them a problem which can be easily done with it...

Pierre.


How to prove it :

If complex number $ z_{1}$,...,$ z_{k}$ did lie on the same side of a some straight line through $ z$,
 then  $ z \minus{} z_{1}$,...,$ z \minus{} z_{k}$ all lie on the same side of a straight line through 0

Double-posting is rude.  If you understand the correspondence bewteen the algebraic operation of "adding a complex number" and the geometric operation of "translating the complex plane by a given vector," this is immediate.


How many perfect squares are divisors of the product $1!\times2!\times3!\times...\times9!$?

[quote="Hokkage"]Rewrite as $2^{17}3^{7}5^{5}7^{3}$. From there it's arranging all the different possibilities of products with exponents that are multiples of 2. So there are 9 possibilities for $2^{17}$, 4 possibilities for $3^7$, 3 possibilities for $5^5$, and 2 possibilities for $7^3$ because the power of 0 is included for all of them. So multiply these together, $9 \times 4 \times 3 \times 2 = 216$ perfect squares that the product is divisible by.[/quote]

Aren't you overcounting there? You count the power of $0$ for each of 2, 3, 5, and 7, but $2^0=3^0=5^0=7^0$. Too many? Or am I not understanding what you did there?

No, his logic is fine.  The zero powers just represent the squares that don't have a factor of $2$, or don't have a factor of $5$, etc.

in the expression $x = 2^a \cdot 3^b \cdot 5^c \cdot 7^d$ we have $x=1$ only when $a=b=c=d=0$


number theory
Divisibility
prime
IMO
IMO 1999
IMO Shortlist

First of all, if $p=2$, then $x$ is $1$ or $2$. Assume now $p\ge 3$.

Clearly, $x$ must be odd (let's say that $x=2k+1$), and let's assume $x>1$. Let $q$ be the smallest prime divisor of $x$. We have $q|((p-1)^2x-1,(p-1)^{q-1}-1)=(p-1)^2-1=p(p-2)$. Assume $q\ne p$. We find that $q|p-2$. At the same time, we have $q|(p-1)^x+1=(p-1)^{2k+1}+1=[(p-1)^{2k}-1](p-1)+p$, so $q|p$, which contradicts the fact that $q|p-2$ and $q$ is odd. This means that $q=p$, so $x\in\{p,2p\}$, and since it's odd, we have $x=p$.

We now have to find those odd primes $p$ s.t. $p^{p-1}|(p-1)^p+1$. After expanding the binomial on the right, we find that the expression on the right is $p^2+kp^3$, so $p-1\le 2$, meaning that the only odd prime satisfying this is $p=3$ (it it does satisfy the relation, since $3^2|2^3+1$). The solutions are then $(1,p)$ for any prime $p$, $(2,2)$ and $(3,3)$.

[b]OFFICIAL SOLUTION[/b]

Clearly we have the solutions $(1,p)$ and $(2,2)$, and for every other solution $p \geq 3$. It remains to find the solutions $(x,p)$ with $x \geq 2$ and $p \geq 3$. We claim that in this case $x$ is divisible by p and $x y 2p$, whence $x = p$. This will lead to

\[p^{p-1}|(p-1)^{p}+1=p^{2}\left(p^{p-2}-{p \choose 1}p^{p-3}+
\cdots + -{p \choose p-3}p-{p \choose p-2}+1\right)\]

therefore, because all the terms in the brackets excepting the last one is divisible by $p$,$p-1 \leq 2$. This leaves only $p=3$ and $x=3$. Let us prove now the claim. Since $(p-1)^{x}+1$ is odd, so is $x$ (therefore $x < 2p$). Denote by q the smallest prime divisor of $x$. $q|(p-1)^{x}+1$ we get $(p-1)^{x} \equiv -1 \pmod {q}$ and $(q,p-q)=1$. But $(x,p-q)=1$ (from the choice of q) leads to the existence of integers $u,v$ such that $ux+v(q-1)=1$, whence $p-1 \equiv (p-1)^{ux}$. $(p-1)^{v(q-1)} \equiv (-1)^{u} \cdot 1^{v} \equiv -1 \pmod {q}$, because $u$ must be odd. This shows that $q|p$, therefore $q=p$. In conclusion the required solutions are $(2,2), (3,3)$ and $(1,p)$, where $p$ is an arbitrary prime.

[quote="grobber"]

 At the same time, we have $q|(p-1)^{x}+1=(p-1)^{2k+1}+1=[(p-1)^{2k}-1](p-1)+p$, so $q|p$, which contradicts the fact that $q|p-2$ and $q$ is odd. [/quote]
  i dont get  this  why  does q divide  p.  please  someone explain.

[quote="orl"]Find all the pairs of positive integers $ (x,p)$ such that p is a prime, $ x \leq 2p$ and $ x^{p \minus{} 1}$ is a divisor of $ (p \minus{} 1)^{x} \plus{} 1$.[/quote]
First the case where $ p\equal{}2$: $ x \mid 2$. So there are solutions $ (p,x) \equal{} (2,1)$ and $ (p,x) \equal{} (2,2)$.
Then the case where $ x\equal{}1$. (I will use that $ x$ has prime divisors later) $ 1^{p\minus{}1} \mid (p\minus{}1)^1 \plus{} 1 \iff 1 \mid p$ always holds. So $ (1,p)$ are also solutions.
$ x^{p\minus{}1} \mid (p\minus{}1)^x \plus{} 1 \mid (p\minus{}1)^{2x} \minus{} 1$. Let $ q$ be the smallest primedivisor of $ x$. Then $ (p\minus{}1)^{2x} \equiv 1 \bmod q \Rightarrow (p\minus{}1)^{(2x,q\minus{}1)} \equiv 1 \bmod q$. But $ (2x,q\minus{}1) \le 2(x,q\minus{}1) \equal{} 2$. So $ q \mid (p\minus{}1)^2\minus{}1 \equal{} p(p\minus{}2)$.
If $ q \mid p$ then $ q\equal{}p$. Since $ x$ is odd and $ x \leq 2p$ we see that $ x\equal{}p > 2$. Then $ p^{p\minus{}1} \mid (p\minus{}1)^p \plus{} 1 \equal{} (p\minus{}1)^p \minus{} (\minus{}1)^p$
It is well known that $ v_p(a^n\minus{}b^n) \equal{} v_p(n) \plus{} v_p(a\minus{}b)$ when $ a \equiv b \bmod p$ and $ (ab,p)\equal{}1$.
Hence $ v_p( (p\minus{}1)^p \minus{} (\minus{}1)^p ) \equal{} v_p(p) \plus{} v_p(p\minus{}1\minus{}(\minus{}1))\equal{}2$. Hence $ p\minus{}1 \le 2$. And then $ p\equal{}3$ gives the solution $ (x,p)\equal{}(3,3)$.
Now assume that $ q \mid p\minus{}2$. Then $ q^{p\minus{}1} \mid (p\minus{}1)^{2x} \minus{} 1^{2x}$.
So $ v_q( (p\minus{}q)^{2x} \minus{} 1^{2x} ) \equal{} v_q(p\minus{}2) \plus{} v_q(2x) \ge p\minus{}1$.
But since $ q$ is odd: $ v_q(2x) \equal{} v_q(x)$. And $ q \ge 3$. Hence $ v_q(n) \le log_3(n)$ when $ n \in \mathbb{N}$. So:
$ log_3(p\minus{}2) \plus{} log_3(x) \ge p\minus{}1$.
$ x \le 2p$: $ log_3(p\minus{}2) \plus{} log_3(2p) \ge p\minus{}1 \iff 2p^2\minus{}4p \ge 3^{p\minus{}1}$
Let $ f(p) \equal{} 3^{p} \minus{} 2(p\plus{}1)^2\plus{}4(p\plus{}1) \equal{} 3^p \minus{} 2p^2\plus{}2$. Then $ f(p\minus{}1) \le 0$.
$ f'(p) \equal{} \ln (3) \cdot 3^p \minus{}4p$ and $ f''(p) \equal{} \ln^2(3) \cdot 3^p > 0$
But $ f'(2) \equal{} \ln (3) \cdot 3^2 \minus{} 4 \cdot 2 > 3^2 \minus{} 4 \cdot 2 \equal{} 1 > 0$. Since $ f''(p) > 0$ we see that $ f(p)$ is increasing when $ p \ge 2$. But $ f(2) \equal{} 3^2\minus{}2\cdot2^2\plus{}2 \equal{} 3 > 0$
Hence: When $ p \ge 3$ we see that $ f(p) > 0$. So $ q \mid p\minus{}2$ doesn't give any solutions. QED

[hide]It took me less than 15 minutes to find this solution without pen and paper. (Except that i messed up some deratives at the end.) And surprisingly a bit longer than that to write it up - nearly twenty.[/hide]

Setting $n=1$ we get the solutions $(1,p)$ with $p$ prime. For $p\in\{2,3\}$ we find that $(2,2)$ and $(3,3)$ are solutions too. Now let $n>1$ and $p>3$, then $n$ has to be odd.

Case 1. $n$ is a prime power, so write $n=q^\alpha$. Then we get $(p-1)^{q^\alpha}\equiv -1 \mod q \Leftrightarrow p\equiv 0 \mod q \Leftrightarrow p=q$, implying that $\alpha=1$. Now $(p-1)^p+1=\sum_{i=0}^p \binom{p}{i} p^i (-1)^{p-i}+1\equiv \sum_{i=3}^{p-2} \binom{p}{i}p^i (-1)^{p-i} - \frac{p-1}{2} p^3+p^2 \equiv 0 \mod p^{p-1}$
and as the LHS is divisible by $p^2$ but not by $p^3$, the congruence cannot hold, so there are no solutions.

Case 2. $n$ has at least two distinct prime factors. Let $q$ be the smallest prime divisor of $n$, then $n=a\cdot q^\alpha$ with $\gcd(q,a)=1$ and $a\ge 3$, so $3q^\alpha<2p$. Now we have $(p-1)^{aq^\alpha}\equiv -1 \mod q^{\alpha(p-1)}$. Squaring, we get $(p-1)^{2aq^\alpha}\equiv 1 \mod q^{\alpha(p-1)}$. As $ord_{q^{\alpha(p-1)}}(p-1)|\gcd\left(2aq^\alpha,\varphi\left(q^{\alpha(p-1)}\right)\right)=\gcd\left(2aq^\alpha,(q-1)q^{\alpha(p-1)-1}\right)=2q^\alpha$ we also have $(p-1)^{2q^\alpha}\equiv 1 \mod q^{\alpha(p-1)}\Leftrightarrow\left((p-1)^{q^\alpha}-1\right)\left((p-1)^{q^\alpha}+1\right)\equiv 0 \mod q^{\alpha(p-1)}$.
As $gcd\left((p-1)^{q^\alpha}-1,(p-1)^{q^\alpha}+1\right)=1$ we get $(p-1)^{q^\alpha}\equiv \pm 1 \mod q^{\alpha(p-1)}$. If $(p-1)^{q^\alpha}\equiv 1 \mod q^{\alpha(p-1)}$ it follows that $(p-1)^{aq^\alpha}\equiv 1 \equiv -1 \mod q^{\alpha(p-1)}$, a contradiction. But now $q^{\alpha(p-1)}|(p-1)^{q^\alpha}+1$. We know from Catalan's conjecture that equality cannot hold here, further $(q^\alpha)^{p-1}>(p-1)^{q^\alpha}\Leftrightarrow\frac{\ln(q^\alpha)}{q^\alpha}>\frac{\ln(p-1)}{p-1}$ which is clearly true, as $f'(x)= \left(\frac{\ln(x)}{x}\right)'=\frac{1-\ln(x)}{x^2}$, so $f(x)$ is strictly decreasing for $x>e$. We conclude that there are no more solutions.

Hence, $(1,p),(2,2),(3,3)$ are the only solutions. $\square$

Here is my solution(not exactly written up in the most organized way):
[hide]Assume $p \geq 3$.
If $x=2$, then $2^{p-1}|(p-1)^2+1$, which is a contradiction since the two sides have different parity. Similarly, $x \neq 2p$.
If $x=p$, then $p^{p-1}|(p-1)^p+1=p^2(p^{p-2}-{p\choose 1}+...-1) \not\equiv 0 \pmod{p^3}$. Hence, $p \leq 3$ and checking $(2,2)$ and $(3,3)$ are solutions.
Therefore, we assume $gcd(x,p)=1$ with $x \neq 2$. By considering parity, $x$ must be odd. Let $x=2k+1$ for some nonnegative $k$. Then $(p-1)^{2k+1}+1=j(2k+1)^{p-1}$ for some integer $j$. Again, $j$ must be odd. Note that $(p-1)^{2k+1}+1 \equiv 0 \pmod{p}$. Hence, $j=mp$ for an odd integer $m$.
Therefore,
$(p-1)^{2k+1}+1=mp(2k+1)^{p-1} \implies p^{2k}-{2k+1\choose 1}p^{2k-1}+...+{2k+1\choose 2k-1}p=(2k+1)(m(2k+1)^{p-2})-1 \implies p|m(2k+1)^{p-2}-1 \implies m(2k+1)^{p-2}=1$. Hence $m=1$ and $p=2$ or $m=1$ and $2k+1=1$. The first yields an even value of $j$, contradiction. The second yields solutions $(1,p)$ where $p$ is any prime.
The only solutions are $(2,2)$, $(3,3)$, and $(1,p)$ for a prime $p$.[/hide]

Once the cases $x=1$ and $p\mid x$ have been dealt with using, for example, LTE (giving solutions of $\left(1,p\right),\left(2,2\right)$ and $\left(3,3\right)$) and it has been noted that $x$ is otherwise odd, another way to finish it off is to use orders:

$x^{p-1}\mid\left(p-1\right)^{x}+1\mid\left(p-1\right)^{2x}-1$. Thus if $q$ is the smallest a prime divisor of $x$ (the case $x=1$ has already been dealt with) then we have that $q\mid\left(p-1\right)^{x}+1\Rightarrow q\nmid\left(p-1\right)^{x}-1$ ($x$ is odd means $q\neq2$) and $q\mid\left(p-1\right)^{2x}-1$. Thus $\text{ord}_{q}\left(p-1\right)\nmid x$ and $\text{ord}_{q}\left(p-1\right)\mid2x$ hence, as $x$ is odd, $\text{ord}_{q}\left(p-1\right)$ is twice a factor of $x$ so $\frac{\text{ord}_{q}\left(p-1\right)}{2}$ is a factor of $x$ so is either $1$ or at least $q$.

Now by FLT: $\frac{\text{ord}_{q}\left(p-1\right)}{2}\mid\text{ord}_{q}\left(p-1\right)\mid q-1$ so  $\frac{\text{ord}_{q}\left(p-1\right)}{2}\leq q-1\Rightarrow\frac{\text{ord}_{q}\left(p-1\right)}{2}=1\Rightarrow\text{ord}_{q}\left(p-1\right)=2$.

Now $\text{ord}_{q}\left(p-1\right)=2\Rightarrow\left(p-1\right)^{2}\equiv1\mod{q}\Rightarrow\left(p-1\right)^{x-1}\equiv1\mod{q}$ ($x$ is odd means $x-1$ is even). Thus $\left(p-1\right)^{x}\equiv p-1\mod{q}\Rightarrow\left(p-1\right)^{x}+1\equiv p\mod{q}$. But $q\mid\left(p-1\right)^{x}+1$ so $q\mid p\Rightarrow q=p\Rightarrow p\mid x$ which is a case that has already been dealt with.

frill,your solution is really nice.....I like it.... BTW I don,t know why no one thought of using orders earlier....

[quote="Davron"]@all : can you please explain :-)

$q|[(p-1)^2x-1,(p-1)^{q-1}-1)=(p-1)^2-1$

Sincerely Davron[/quote]
$q|(p-1)^{2x}-1$ because $(p-1)^{2x}-1=((p-1)^x+1)((p-1)^x-1)$ and $q|(p-1)^{q-1}-1$ from fermat's little theorem,so $q$ will divide GCD of them

First, note that if $x = 1$, then the desired relation trivially holds for all $p.$ Hence, the pair $(1, p)$ is valid for all primes $p.$ Now, let us consider the cases of $x = p$ and $p = 2, 3.$ If $x = p \ne 2, 3$, then we must have $p^{p - 1} \mid (p - 1)^p + 1.$ But note that $p \mid (p - 1) + 1$, so we may apply LTE to find that $v_p\left((p - 1)^p + 1^p\right) = v_p(p) + v_p(p) = 2.$ It follows that $p - 1 \ge 2$, which is impossible from the assumption that $p \ne 2, 3.$

If $p = 3$, we are searching for $x \in \{1, 2, 3, 4, 5, 6\}$ such that $x^2 \mid 2^x + 1.$ By testing these six possibilities, we find the solutions $(1, 3), (3, 3).$ If $p = 2$, we are searching for $x \in \{1, 2, 3, 4\}$ such that $x \mid 2.$ Thus we obtain the solutions $(1, 2), (2, 2).$ Furthermore, note that if $x$ is even, then $x^{p - 1} \mid (p - 1)^x + 1 \implies p - 1$ is odd, and so $p = 2$, which is a case that was already covered. Henceforward, we may assume that $x$ is odd.

Now, suppose that $x > 1$, and let $q \ne 2, p$ be the least prime divisor of $x.$ Then we have the relation \[(p - 1)^x \equiv -1 \pmod{q^{p - 1}} \implies (p - 1)^x \equiv -1 \pmod{q} \implies (p - 1)^{2x} \equiv 1 \pmod{q}.\] Hence, if we let $d = \text{ord}_q(2)$, it is well-known that $d \mid 2x.$ Furthermore, since $p - 1$ and $q$ are clearly relatively prime, we derive that \[(p - 1)^{q - 1} \equiv 1 \pmod{q} \implies d \mid q - 1 \implies d \le q - 1.\] Now, note that if $d \ne 2$, then there is some prime divisor of $d$ that is also a divisor of $x.$ However, this is impossible, because said divisor would have to be less than $q$ (because $d \le q - 1$), and we assumed that $q$ was the least prime divisor of $x.$ Therefore, we conclude that $d = 2.$ It follows that \[(p - 1)^2 \equiv 1 \pmod{q} \implies p(p - 2) \equiv 0 \pmod{q} \implies p - 2 \equiv 0 \pmod{q},\] because we assumed that $q \ne p.$ It follows that $(p - 1)^x + 1 \equiv 1^x + 1 \equiv 2 \pmod{q}.$ However, this contradicts $(p - 1)^x + 1 \equiv 0 \pmod{q}$, so we conclude that there are no such solutions.

In summary, the desired pairs are $(2, 2), (3, 3)$, and $(1, p)$ for any prime $p.$

[quote=1999 ISL NT 1]
Find all the pairs of positive integers $(x,p)$ such that p is a prime, $x \leq 2p$ and $x^{p-1}$ is a divisor of $ (p-1)^{x}+1$.
[/quote]

If $x=p$ then we have $p^{p-1} \mid (p-1)^p+1$. Since $p \mid (p-1)+1$, by LTE we know that $v_p((p-1)^p+1) = v_p((p-1)+1)+v_p(p) = 2$. Therefore, $p-1 \le 2 \implies p=2,3$. These yield the valid pairs $\boxed{(2,2), (3,3)}$. If $x=1$ then all pairs in the form $\boxed{(1,p)}$ where $p$ is a prime work. Now assume $p >2, x>1$ and $p \neq x$.

We have $x^{p-1} \mid (p-1)^x+1 \mid (p-1)^{2x}-1$. Notice that $x$ must be odd because $(p-1)^x+1$ is odd ($p >2$). Therefore, $\gcd(x^{p-1}, (p-1)^x-1)=1$ because $x^{p-1} \mid (p-1)^x+1$ and the smallest prime that divides $x^{p-1}$ is greater than $2$. Then if $q$ is the smallest prime factor of $x$, we know that $\text{ord}_q(p-1) \mid 2x$ and $\text{ord}_q(p-1) \nmid x$. Since $x$ is odd, we know that $\text{ord}_q(p-1) \ge 2q$ or $\text{ord}_q(p-1)=2$. However, since $\phi(q) = q-1$, we know that $\text{ord}_q(p-1) \mid q-1$ so we must have $\text{ord}_q(p-1)=2$. Hence, $(p-1)^2 \equiv 1 \pmod{q}$. Then $(p-1)^x+1 \equiv 0 \pmod{q} \implies p \equiv 0 \pmod{q}$. Since $p$ is prime, $p=q$ so $p$ must also equal $x$ since $x \le 2p$, which goes against our assumptions. Therefore, we are done. $\blacksquare$

Hey, noob here. A bit off-topic question, but is there something wrong with this statement below? (Not that it's useful)

This is for cases $x > 1, p > 2$.
$x^{p - 1} \mid \left(p - 1\right)^x + 1 \Rightarrow \nu_p(x^{p - 1}) \leq \nu_p(\left(p - 1\right)^x + 1^x) = \nu_p(p) +\nu_p(x) = 1 + \nu_p(x) \Rightarrow \left(p - 2 \right)\nu_p(x) \leq 1$

My solution: If $p=2$, then $x \mid 2 \Rightarrow x=1,2$. So from now on assume that $p$ is odd.

Now, $x^{p - 1} \mid \left(p - 1\right)^x + 1 \Rightarrow (p-1) \cdot \nu_p(x) = \nu_p(x^{p - 1}) \leq \nu_p(\left(p - 1\right)^x + 1) = \nu_p(p) +\nu_p(x) = 1 + \nu_p(x) \Rightarrow \left(p - 2 \right)\nu_p(x) \leq 1$.

CASE-1 ($\nu_p(x) \geq 1$): $p-2 \leq 1 \Rightarrow p \leq 3 \Rightarrow p=3$.

And, $p \mid x \Rightarrow 3 \mid x$ and $x \leq 2p = 6$ $\Rightarrow x=3$ or $6$. But $x^2 \mid 2^x+1 \Rightarrow x=3$

CASE-2 ($\nu_p(x)=0$): Notice that $x=1$ works for all $p$, so from now on assume that $x \not= 1$.

Let $m$ be a prime divisor of $x$. Note that as $p \nmid x$, so $p \not= m$. Then, $(p-1)^x+1 \equiv 0 \pmod{m} \Rightarrow (p-1)^{2x} \equiv 1 \pmod{m}$

Thus, $ord_m(p-1) \mid 2x$. Also $ord_m(p-1) \mid \phi(m) \Rightarrow ord_m(p-1) \mid m-1$.

Also as $ord_m(p-1) \leq m-1$, so $ord_m(p-1) \mid gcd(m-1,2x)$. But as $m \mid x \Rightarrow m-1 \nmid x$.

SUBCASE-1 ($m \not= 3$): $m-1 \nmid 2 \Rightarrow gcd(m-1,2x)=1 \Rightarrow ord_m(p-1) = 1 \Rightarrow p \equiv 1 \pmod{m}$

$\Rightarrow (p-1)^x+1 \equiv 1 \equiv 0 \pmod{m} \longrightarrow CONTRADICTION$.

SUBCASE-2 ($m=3$): $m-1 \mid 2 \Rightarrow gcd(m-1,2x) =2 \Rightarrow ord_m(p-1)=1 \text{or} 2$.

By a similar argument as in subcase-1, $ord_m(p-1) \not= 1 \Rightarrow ord_m(p-1) = 2 \Rightarrow (p-1)^2 \equiv 1 \pmod{m}$

$\Rightarrow p(p-2) \equiv 0 \pmod{m} \Rightarrow p-2 \equiv 0 \pmod{m} \Rightarrow (p-1)^x+1 \equiv 2 \equiv 0 \pmod{m} \longrightarrow CONTRADICTION$.

Thus, The only solutions are $(x,p)=(1,p),(2,2),(3,3)$.

If $x=1$, then all primes $p$ work. Suppose that $x>1$, and take the smallest prime $q$ such that $q\mid x$. We have $$(p-1)^x\equiv -1\pmod{q},$$ so $\mathrm{ord}_q(p-1)\mid 2x$ and $\mathrm{ord}_q(p-1)\mid q-1$. Therefore $$\mathrm{ord}_q(p-1)\mid \gcd(2x,q-1).$$ The prime divisors of $\gcd(2x,q-1)$ divide $2x$ but are less than $q$, and if they are not $2$, then they divide $x$, contradicting the minimality of $q$. Thus $2$ is the only possible prime divisor of $\gcd(2x,q-1)$, i.e. $\gcd(2x,q-1)\in \{1,2\}$.

    Suppose $x$ is odd, so $q-1$ is even, and we know that $\gcd(2x,q-1)=2$. This gives $\mathrm{ord}_q(p-1)\in \{1,2\}$. If $\mathrm{ord}_q(p-1)=1$, then $(p-1)^x\equiv 1\pmod{q}$, contradiction since $q>2$. If $\mathrm{ord}_q(p-1)=2$, then $(p-1)^2\equiv 1\pmod{q}$, so $p(p-2)\equiv 0\pmod{q}$. Then $q\mid p-2$ gives contradiction as seen above, so $q\mid p$. Since $p$ is a prime, we know $q=p$, thus $p\mid x$. If anything greater than or equal to $2$ divides $\tfrac{x}{p}$, then $x\geq 2p$; since we are given $x\leq 2p$, we have $x=2p$, contradiction since we assumed $x$ is odd. So $\tfrac{x}{p}$ is not divisible by anything greater than or equal to $2$, i.e. $x=p$. We now have $p^{p-1}\mid (p-1)^p+1$. We can write $$(p-1)^p+1=p^p+\binom{p}{1}p^{p-1}(-1)+\dots+\binom{p}{p-3}p^3(-1)^{p-3}+\binom{p}{p-2}p^2(-1)^{p-2}+\binom{p}{p-1}p(-1)^{p-1}.$$ Since $\tbinom{p}{p-1}=p$ and $\tbinom{p}{p-2}=p\cdot \tfrac{p-1}{2}$, and $\tfrac{p-1}{2}$ is an integer due to our assumption that $x$ is odd, we can write $(p-1)^p+1=p^3(k)+p^2$ for some integer $k$. Therefore $p^2\mid (p-1)^p+1$ but $p^3\nmid (p-1)^p+1$, so $p^{p-1}\mid (p-1)^p+1$ is false for $p>3$. We can check that $p=2$ and $p=3$ work.

    If $x$ is even, then $q=2$, and $\gcd(2x,q-1)=1$, so $\mathrm{ord}_q(p-1)=1$. This gives a contradiction, as we have already seen before. Hence the solutions are $(2,2)$, $(3,3)$, and $(1,p)$, where $p$ is any prime.

We use [url=https://artofproblemsolving.com/community/c6h60740p366466]IMO 1990 P3[/url] to solve this.

[hide=Page 1][img]https://i.imgur.com/RNKQPN9.jpg[/img][/hide] [hide=Page 2][img]https://i.imgur.com/wuhUkU4.jpg[/img][/hide] [hide=Page 3][img]https://i.imgur.com/sCkzVYu.jpg[/img][/hide]

handwritten solution images attached

If $x=1$, this always works. Otherwise, consider the smallest prime $q$ dividing $x$. Then
\[q\mid (p-1)^x+1\mid (p-1)^{2x}-1.\]
Define $a=\text{ord}_q(p-1)$. Then $a\mid 2x$ and $a\mid q-1$. But $\gcd(2x,q-1)\mid 2$, so $a\mid 2$.

If $a=1$, then \[p-1\equiv 1\pmod q\rightarrow q\mid 2\rightarrow q=2.\] This implies that $p-1$ is odd, which can only be true when $p=2$. In that case, the problem reduces to $x\mid 2$, so $x\in\{1,2\}$. Since we were assuming $x\ne 1$, we just get $(x,p)=(2,2)$ for this case, which works.
If $a=2$, then \[p-1\equiv -1\pmod q\rightarrow q\mid p\rightarrow q=p.\] Then let $b=\nu_q(x)$. Taking $\nu_q$ of both sides,
\[b(p-1)\le\nu_p(p-1+1)+b\rightarrow b(p-2)\le 1\rightarrow p\le 3.\] $p=2$ was already covered in the previous case, and $p=3$ reduces to IMO 1990/3([url=https://artofproblemsolving.com/community/c6h60740p27004701]link[/url] to my solution), which has solutions $x=1$ and $x=3$. Since we were assuming $x\ne 1$, the only solution for this case is $(x,p)=(3,3)$, which works.

Combining all cases, our answer is $\boxed{(x,p)=(1,p),(2,2),(3,3)}$ for any prime $p$.

Let $p_1 \mid x$ for minimal $p_1$. Then, $$p_1 \mid (p-1)^x + 1 \implies p_1 \mid (p-1)^{\gcd(x, p_1-1)} + 1 = p,$$ so $p_1 = p$. Then, notice that $$\nu_p((p-1)^x + 1) = 1 + \nu_p(x),$$ so thus $$(p-1)\nu_p(x) \leq \nu_p(x) + 1.$$ So we must have $p \leq 3$, for which $(2, 2)$ and $(3, 3)$ are solutions. (See IMO 1990/3.) On the other hand, if $x=1$, then $(1, p)$ also works.

PUTNAM 1972/A5 and IMO 1990/3 have got partners, I see...

[i]Solution:[/i] The only possible solution pairs $(x,p)$ are
    [list]
        [*] $(1,p)$ for any prime $p$,
        [*] $(2,2)$ and $(3,3)$
    [/list]
which clearly work. We assume $x > 1$ and $p>2$ for the rest of the solution and show $(3,3)$ is the only possible solution. Checking $x = 1$ and $p = 2$ by hand is easy.

Note that $x$ is odd. Choose $q$ to be the minimal prime divisor of $x$. We would get
    \begin{align*}
        (p-1)^{2x} &\equiv 1 \pmod{q} \\
        (p-1)^{q-1} &\equiv 1 \pmod{q}.
    \end{align*}
Repeating the same technique from the quoted PUTNAM problem, we would get $q \mid (p-1)^{\gcd(2x,q-1)}$. Since $q$ is the smallest prime divisor of $x$, then we would have $\gcd(2x,q-1) = 2$. This would give
    \begin{align}
    q \mid (p-1)^2 - 1 \iff q \mid p^2 - 2p. \label{1}
    \end{align}
We will split cases here. If $q \mid p$, then we would $q = p$ since both are primes which leads to $x \in \{p,2p\}$. $x = 2p$ would be a contradiction on the parity of $x$. For $x = p$, then we have to find all primes such that
    \[p^{p-1} \mid (p-1)^p + 1 \implies p-1 \le \nu_p((p-1)^p + 1) \]
Apply ``Lifting the Exponent Lemma'' to get $p-1 \le 2 \implies p = 3$, which again works.

Finally, if $q \nmid p$, then we would have $p \equiv 2 \pmod{q}$ due to $(1)$. Put this in $(p-1)^x \equiv -1 \pmod{q}$ to get $2 \equiv 0 \pmod{q} \implies q = 2$ which is a contradiction on $x$ being odd. $\blacksquare$

We claim that the only solutions are $(1,p)$ for all primes $p$, $(2,2)$, and $(3,3)$.

Case 1 : $x=1$.
Clearly, for $x=1$, all $p$ work.

Case 2: $p=2$.
By inspection (aka trial and error) we find that only $x=1$ and $x=2$ work.

Case 3: $p>2$, $x>1$.

3a. [color=#9a00ff]$x$ is divisible by $p$[/color]
[color=#9a00ff]Let $e_k=\nu{}_p(x)$. [/color]

[color=#9a00ff]Since $p>2$, $p$ must be odd. If $p$ is odd, then $(p-1)^x+1$ is odd, implying that $x^{p-1}$ is odd. Therefore, $x$ is odd,[/color] so by LTE, we have that
\[\nu_{p}((p-1)^x+1^x)=\nu_{p}(p)+\nu_{p}(x)\]
which must be equal to $e_k+1$.

We have that $(p^{e_k})^{p-1}\mid{}(p-1)^x+1^x$, so $e_k(p-1)\le{}e_k+1$. This only works when $e_k=1$ and $p=3$, or $p=2$. Since the latter is extraneous since we already assumed $p>2$, by inspection on $p=3$, we find our only solution such that $x>1$ is $(3,3)$.

[color=#9a00ff]3b. $x$ is not divisible by $p$.
Clearly, if $p>2$, then $x$ is odd.

We claim that if $x>1$ and $p>2$, $x$ must be a multiple of $p$. Consider the smallest prime that divides $x$. Call this prime $q$.

$q\mid{}(p-1)^x+1$, therefore the order of $p-1$ modulo $q$ is even and a factor of $2x$. The order of $p-1$ modulo $q$ must also be a factor of $q-1$ by Euler's totient function. This means that the order of $p-1$ modulo $q$ must be $2$. This is because $q$ is the smallest prime dividing $x$, therefore $q-1$ and $x$ are relatively prime.

By the original problem statement, we have $q\mid{}(p-1)^x+1$. If $x$ is odd, this reduces to $q\mid{}(p-1)+1$, since the order of $p-1$ modulo $q$ is $2$. Therefore we have that $q=p$, implying that for $x>1$ and $p>2$, $x$ must always be a multiple of $p$.

Therefore our only solutions are in the form of $(1,p)$, $(2,2)$, and $(3,3)$, and we are done. [/color]

[quote=peppapig_]Checked by [b]Gumball[/b].

We claim that the only solutions are $(1,p)$ for all primes $p$, $(2,2)$, and $(3,3)$.

Case 1 : $x=1$.
Clearly, for $x=1$, all $p$ work.

Case 2: $p=2$.
By inspection (aka trial and error) we find that only $x=1$ and $x=2$ work.

Case 3: $p>2$, $x>1$.
Let $p_1$ be a prime such that $p_1^{e_k}\mid{}x$ for some integer $e_k>1$ and $e_k$ is as large as possible. By LTE, we have that
\[\nu_{p_1}((p-1)^x+1^x)=\nu_{p_1}(p)+\nu_{p_1}(x)\]
which either equals $e_k$ or $e_k+1$, since $p$ is prime.

3a. $p_1=p \rightarrow{} \nu_{p_1}((p-1)^x+1^x)=e_k+1$.
We have that $(p_1^{e_k})^{p-1}\mid{}(p-1)^x+1^x$, so $e_k(p-1)\le{}e_k+1$. This only works when $e_k=1$ and $p=3$, or $p=2$. Since the latter is an extraneous case since we already assumed $p>2$, by inspection on $p=3$, we find our only solution such that $x>1$ is $(3,3)$.

3b.  $p_1\neq{}p \rightarrow{} \nu_{p_1}((p-1)^x+1^x)=e_k$
Similarly, we have that $e_k(p-1)\leq{}e_k$ meaning that $p=2$, which is again extraneous.

Therefore our only solutions are in the form of $(1,p)$ for all primes $p$, $(2,2)$, and $(3,3)$, and we are done.[/quote]

what i dont hold any credibility of this solution. i read it in like 30 seconds.

If $x = 1$, then all $p$ work. If $p = 2$, then $x = 2$ works. Assume now that $x,p > 2$. Let $q$ be the minimal prime divisor of $x$. We have that \[ \text{ord}_q(p-1) \mid 2x, q-1 \implies \text{ord}_q(p-1) \mid 2 \implies q \mid p(p-2).\] If $q \mid p$, then $x = p$ and $x = 2p$ are the only possibilities, but $x = 2p$ fails by parity. If $x = p$, then \[p^{p-1} \mid (p-1)^p + 1 \implies p-1 \le \nu_p((p-1)^p + 1) \] so by LTE $p - 1 \le 2 \implies p = 3$, which works and gives $x = 3$.
If $p \equiv 2 \pmod  q$, then $(p-1)^x \equiv -1 \pmod q \implies 2 \equiv 0 \pmod  q \implies q = 2$, which again fails due to parity.

To summarize, our solutions are $\boxed{(1, p), (2, 2), (3, 3)}$

[quote=orl]Find all the pairs of positive integers $(x,p)$ such that p is a prime, $x \leq 2p$ and $x^{p-1}$ is a divisor of $ (p-1)^{x}+1$.[/quote]

x is odd else LHS even and RHS odd.
Assume p=2, then we have x|2, x=1,2.
Now assume x is not 1 or 2, and we also note that obviously all pairs (1,p) work.
We claim the answers are $\boxed{(x,p)=(1,p), (2,2), (3,3)}$. Consider the smallest prime q | x: $$(p-1)^x\equiv-1\pmod q\implies(p-1)^2\equiv(p-1)^{\gcd(2x, q-1)} \equiv 1 \pmod q\implies p \equiv \{0,2\} \pmod q;$$
the latter implies -1=$(p-1)^x$ = 1 mod q implies q=2, contradiction, so p=q|x.
Looking at v_p with LTE, (p-1)v_p(x)\le v_p(x)+1 implies p=3 which gives x=3.

Long solution with unnecessary claims (probably), though very quick and easy to find.

We can see $x = 1$ works for all primes $p$ so disregard this case from now on.

Note that we want,
\begin{align*}
(p-1)^x \equiv - 1 \pmod{x^{p-1}}
\end{align*}
Consider the smallest prime $q \mid x$. Then we have,
\begin{align*}
(p-1)^{2x} \equiv 1 \pmod{q}
\end{align*}
Then $\text{ord}_{q}(p-1) \mid \gcd(2x, q - 1) = 2$. Assume that $\text{ord}_{q}(p-1) = 1$. Then we find that $p \equiv 2 \pmod{q}$. However then we require that $(p-1)^x + 1 \equiv 2 \equiv 0 \pmod{q}$ implying $q = 2$. Then plugging back in we wish to find solutions to $x \mid 2$ so $x = 2$ works.

Now in our second case we must have $\text{ord}_{q}(p-1)  = 2$. Then we have,
\begin{align*}
p^2 - 2p &\equiv 0 \pmod{q}\\
\iff p(p - 2) &\equiv 0 \pmod{q}
\end{align*}
Then as we have alread considered $p \equiv 2$, we need $p \equiv 0 \pmod{q}$. However as $p$ is prime we need $p = q$ and hence $p$ is the smallest prime divisor of $x$. Now note LTE we have $\nu_p((p-1)^x + 1) = 1 + \nu_p(x)$. Also we easily find that $\nu_p(x^{p-1}) = \nu_p(x) \cdot (p-1)$. Then we obviously need,
\begin{align*}
1 + \nu_p(x) &\geq  (p-1) \cdot \nu_p(x) \\
\iff 1 &\geq (p-2) \cdot \nu_p(x)
\end{align*}
Which holds if and only if $\nu_p(x) = 0$, $p = 2$ or $p = 3$ and $\nu_3(x) \leq 1$. If $\nu_p(x) = 0$, then $x = 1$ as $p$ is the smallest prime divisor of $x$. Then if $p = 2$ we must have $x \mid 2$ which holds if and only if $x = 2$. Finally if $p = 3$ and $\nu_3(x) = 1$ we have $x^2 \mid 2^x + 1$. However from [url=https://artofproblemsolving.com/community/c6h60740p366466]90IMO3[/url] and orders argument gives that this has solutions only when $x = 3$.

Then our final solution set is $\boxed{\{(1, p), (2, 2), (3, 3)\}}$.

We uploaded our solution [url]https://calimath.org/pdf/IMO1999-4.pdf[/url] on youtube [url]https://youtu.be/DtVQP4OXVCw[/url].

If $x = 1$, then all $p$ work.
For  $p=2$, then $x$ is $1$ or $2$. Assume now $p\ge 3$.
Let $x>1$, then let the samllest prime factor of x be q.
We have $(p-1)^{2x} \equiv 1 \pmod{q}$. This implies $ q-1 \mid 2x$. This forces $q=2.$
Now since $v_2(2x^{p-1}) > v_2(p-1)^x +1) $, the only case to be checked now is $x=p$
$\[p^{p-1} \mid (p-1)^p + 1 \implies p-1 \le \nu_p((p-1)^p + 1) \]  $ $ \implies p-1 \le 2 \implies p\le3$
Now checking for $p=3$. We get a solution as $(3,3)$
Therefore the solutions are  $\boxed{(1, p), (2, 2), (3, 3)}$

 :coolspeak:
Solution without the bound of $x$
If $p=2$, then $x=2$, so for now assume $p\geq 3$
If $x=1$ all $p$ primes work, so also assume $x\geq 2$

Let $q$ be the smallest prime dividing $x$ then $(p-1)^{2x}\equiv 1\pmod q$ and as $(p-1)^{q-1}\equiv 1\pmod q$ then $\operatorname{Ord}_q(p-1)\mid 2\gcd\left(x,\frac{p-1}{2}\right)=2$ so $(p-1)^2\equiv 1\pmod q$ so $p=q$ or $p\equiv 2\pmod q$, the latter gives $(p-1)^x+1\equiv 2\pmod q$ impossible. If $p=q$ then, by Lifting the Exponent $$\nu_p((p-1)^x+1)=\nu_p(p)+v_p(x)\geq (p-1)\nu_p(x)$$ so $1\geq (p-2)v_p(x)\geq (p-2)\cdot 1$ so $p=3$
which gives to find all integers $x$ such that $x^2\mid 2^x+1$ which by [url=https://artofproblemsolving.com/community/c6h60740p366466]IMO 1990/3[/url] only $x=3$ works so the solutions are $\boxed{(x,p)=(1,p),(2,2), (3,3)}$

I was given no condition bounding $x$:

-----

The solution set is $(x,p) \in \{(1,p), (2,2), (3,3)\}$.

Note that if $x=1$, all $p$ work. Also, if $p=2$, we must have $x \mid 2$, which gives the unique solution $(x,p)=(2,2)$. Assume $x>1$ and $p>2$ for the remainder of this solution.

Let $q$ be the smallest prime dividing $x$. We have

\[\operatorname{ord}_q(p-1) \mid \gcd(2x,q-1) = 2.\]

Hence,

\[(p-1)^2 \equiv 1 \pmod{q} \iff p(p-2) \equiv 0 \pmod{q}.\]

Hence, $p \equiv 0,2 \pmod{q}$. The latter gives

\[(p-1)^x+1 \equiv 2 \pmod{q},\]

implying that $q=2$. However, $(p-1)^x+1$ is odd, so this yields a contradiction.

Otherwise, we have $p \equiv 0 \pmod{q} \iff p=q$, so LTE gives

\[\nu_p((p-1)^x+1) = \nu_p(p)+\nu_p(x) \ge \nu_p(x^{p-1}) = (p-1) \nu_p(x)\]
\[\implies 1+\nu_p(x) \ge (p-1) \nu_p(x) \iff (p-2) \nu_p(x) \le 1.\]

Since $\nu_p(x) \ge 1$, we must have $p=3$.

The problem is now reduced to finding all $x$ such that $x^2 \mid 2^x+1$.

-----

[b][color=#f00]Lemma[/color][/b] The only value $x$ satisfying this is $x=3$.

[i]Proof:[/i] Consider IMO 1990/3. $\square$

-----

Hence, the unique solution here is $(x,p)=(3,3)$. This completes our solution set.

The condition $x \leq 2p$ turns out to be unnecessary. Our solutions are $\boxed{(1,p),(2,2),(3,3)}$. We proceed first by tackling edge cases:
[list]
[*] If $x=1$, $p$ can be any prime.
[*] If $p=2$, $x$ is either 1 or 2.
[*] Otherwise, $p$ is odd, forcing $x$ to be odd. Then we require
\[(p-1) \cdot v_p(x) \leq v_p((p-1)^x+1) = v_p(x) + 1 \implies (p-2) \cdot v_p(x) \leq 1.\]
If $p=3$, IMO 1990/3 tells us $x$ is either 1 or 3.
[*] Otherwise, $\gcd(x,p)=1$. Suppose the least prime divisor of $x$ is $q>2$. Then
\[\operatorname{ord}_q(p-1) \mid 2n, p-1 \text{ but not } n \implies \operatorname{ord}_q(p-1) = 2 \implies p=q,\]
contradiction. $\blacksquare$
[/list]


number theory
least common multiple
superior algebra
superior algebra unsolved

let $ (G,.)$ be a group ,and $ a,b \in G$ such that $ ab\equal{}ba$ and $ <a>$intersection$ <b>$={e}
prove that the order of ab is equal to the last commun multiple of $ ord(a),ord(b)$

[quote="pleurestique"]denote $ o(a) \equal{} m$, $ o(b) \equal{} n$. since $ a$ and $ b$ commute, $ (ab)^k \equal{} a^kb^k$. assume that $ (ab)^k \equal{} 1$. then $ a^kb^k \equal{} 1$, so $ a^k \equal{} b^{ \minus{} k}$. by hypothesis, we must have $ a^k \equal{} b^{ \minus{} k} \equal{} 1$. this means that $ m|k$ and $ n|k$, so $ \mbox{lcm}(m,n)|k$. on the other hand, $ (ab)^{\mbox{lcm}(m,n)} \equal{} 1$, so the order of $ ab$ is indeed $ \mbox{lcm}(m,n)$.

edit: notice that the hypothesis $ \langle a \rangle \cap \langle b \rangle \equal{} \{1\}$ can be relaxed if $ \gcd(m,n) \equal{} 1$.[/quote]
can you prove that if $ \gcd(m,n) \equal{} 1$ then $ \langle a \rangle \cap \langle b \rangle \equal{} \{1\}$?

the order of $ \langle a \rangle \cap \langle b \rangle$ is a common divisor of $ m,n$.


[quote="mna851"]This is essentially a trivial result but it makes for a decent getting started proof.
Prove that in any triangle the largest angle lies opposite the largest side.[/quote]

[hide]Proceed by contradiction[/hide]

[hide] Inscribe the triangle in a circle.  Th longest side cuts off the most arc.  The largest angle subtends the most arc.  Thus the longest side must be opposite the largest angle.

[/hide]


Find all triples $ (p,q,r)$ in primes such that $ p < q < r < p \plus{} 5$.

so find all triples in primes such that they are within 5 of eachother.
(2,3,5) (3,5,7)
Except for 2 you know that primes have to end in 1,3,5,7,9. A number ending in 5 will never be prime because it will always be divisible by 5 : consider the number $ a_1a_2a_3...5$ We can then factor out a 5 because we are in base 10 and 10 is divisible by 5. This turns the number into 5 x k which is not prime.
Thus the only sequences that satisfy the condition will be the two above and those with primes ending in 7,9,1 and 9,1,3. However, in this sequence of 5 numbers (including those between the primes) there must be atleast one which is divisible by 3. For there to only be one multiple of 3 inside the range of 5, 5 + 3k must be greater than p + 5 and less than p so it must = p + 2, or the middle "prime," so we must have 2 multiples of 3. However, if we have two multiples of three than they must differ by three, and if one is on an even number in the interval then the other must be an odd # , one of the so called primes $ \implies$ even # $ \plus{} 3 \equal{} e \plus{} 2 \plus{} 1 \equal{} 2 ( e/2 \plus{} 1) \equal{} 1 \equal{} 2k \plus{} 1 \equal{}$ odd. Therefore such a sequence is not possible and the two found cases are the only ones.

A shorter solution. All primes greater than $ 3$ are either $ 1$ or $ 5$ $ \bmod 6$. Thus if $ p \equal{} 1 \bmod 6$, then $ q,r \equal{} 2,3,4,5$ and without two primes. If $ p \equal{} 5 \bmod 6$ then $ q,r \equal{} 0,1,2,3$ with only one prime.
So the only solution is $ (2,3,5)$ and $ (3,5,7)$


Let a >0.Prove that:
$ (a \plus{} 1)(\sqrt {2 \minus{} a^2 }  \plus{} \sqrt {5 \minus{} a^2 } ) \le 6$ :D

Pretty inequality.  :)

First AMQM for three variables then AMGM for two variables

$ \dfrac{a\plus{}1}{2}\dfrac{\sqrt{2\minus{}a^2}\plus{}\sqrt{5\minus{}a^2}}{3}\le$
$ \dfrac{a\plus{}1}{2}\sqrt{\dfrac{3\minus{}a^2}{2}}\le$
$ \dfrac{7\plus{}2a\minus{}a^2}{8}\equal{}$
$ 1\minus{}\dfrac{(a\minus{}1)^2}{8}\le$
$ 1$

:)


logarithms
real analysis
real analysis unsolved

does someone know if there exists a formula for the sum ?

$\frac{a}{b}+\frac{ac}{b+d}+\frac{ac^{2}}{b+2d}+\frac{ac^{3}}{b+3d}+\ ...+\frac{ac^{n-1}}{b+(n-1)d}$

There isn't a formula. If $|c|<1$, we can write the infinite sum in terms of logarithms, but we can't do anything with the finite sum unless $d=0$.


can someone give me some information about the APMO? I see that the US has participated in it, but I don't know how to like participate or anything. So...perhaps a website or something, please?

I believe that the US takes the top students from the AMC series of tests. I had found it on their website a while ago.

oh. so would that basically be the IMO team with a couple of extra people?

Check here:

http://www.unl.edu/amc/f-miscellaneous/miscarchive.html

Winners and honorable mentions on USAMO take the APMO, if I am not mistaken.

APMO is written in end of March, USAMO is written in end of May
last year's APMO is, IMHO, easier than USAMO, mainly bc you are given LOADS of time to work on the USAMO.  but then again, the first question in the APMO was a direct result from the McLaurin's Symmetric Mean Inequality, hence it is trivial

Yes, I heard something about that.  It's interesting how they got full credit for it.

-interesting_move

why not?  i used it and got full marks for it ;)  two lines, and two minutes :D

How did you do on the other problems Bugzpodder ?

first two fully.  some part marks on the other ones...  how about you?  does belgium participate in APMO?


but I think I am missing something.

Cannot freeken get this one!THe puzzle is this:

When is half of 13 equal 8?   (Hint: different number system)

I have tried this one with different bases (Base 3 Base 5 etc) and in Hex and Octal...I am either missig something or I am way off track.

Anyone get this?

If you'd like a little explanation with that:

  We know:

$\frac{13_n}{2_{10}} = 8_{10}$

  Its best to begin by converting $13_n$ into base 10.

$13_n = 1(n^1) + 3(n^0) = n + 3$

  Now we can divide.

$\frac{n+3}{2}=8$

$n + 3 = 16$

$n=13$

  So we are working in base 13.

This puzzle has little to do with math, it's more of a brainteaser.  Forget about converting the numbers into different bases.  It's a different "number system".

[hide="Hint"]Try roman numerals...[/hide]


inequalities
combinatorics unsolved
combinatorics

Dwarfs of height 1, 2, 3, ..., N are arranged around a circular table in some order. The positive difference of adjacent dwarfs is taken and these sum to T. Find the minimum and maximum value of T.

I found it.
Finding the minimum is easy. I'll write the whole solution when I'll have time.

If a dwarf is bigger than his both neighbour, we call him "big"
If a dwarf is smaller than his both neighbour, we call him "small"
Otherwise, we call him "useless".

First, we see that someone "useless" will be useless in the required sum.
For example, in the sequence 1 - 2 - 3, the sum is (2-1)+(3-2)+(3-1) = 2*(3-1)
I won't formalize it but it's trivial.

Then, you see that if someone is big, it'll appear in the required sum as his double (you see the 2*3 in the previous example).
If he's small, it'll appear has -2 times his height (you see -2 * 1 in the previous example).

So, the minimum for the required sum is at least 2*(N-1) because N will always be a "big" dward and 1 a "small" one. Now you see it's a possible sum : 1-2-3-4-...-N

For the maximum, it's more complicated.
First, there is always a succesion of big and small dwarfs, starting with a small (the 1) and ending with a big (the N). So, there is a bijection between the big and small dwarfs (for exemple, to each small we assign the first big dwarfs on his left). So, the sum is maximum when there is a maximum of big and small dwarfs.

If N is even, the sum is maximal if 1, 2, ..., N/2 are small and N/2 + 1, ..., N are big. This is actually possible with the sequence : N - 1 - (N-1) - 2 - (N-2) - 3 - ...
It gives a sum equal to $ N^2/2$.

The same reasoning gives $ (N^2\minus{}1)/2$ when $ N$ is odd.


geometry rectangle calculus integration perimeter

Each student in a class is asked to draw a rectangle with integral side lengths and a perimeter of 30 units. Each student then calculates the area of the rectangle s/he drew. What is the greatest possible difference of the areas of two of the students' rectangles?

The sum of the length and width of each person's rectangle is 15. The rectangle that ensures the largest area is the rectangle with closest dimensions, which in this case is 7 and 8, so the largest area is 56. The smalest area is the one with the farthest apart numbers, or 1 and 14, so the smallest area is 14. Thus, the positive difference of the greatest and least possible areas is 56-14=42.


inequalities
function
induction
calculus
integration
inequalities unsolved

Can someone [u]please[/u] show me Jensen`s inequality and prove it.

[u][b]Jensen's Inequality[/b][/u]
If a function $f$ is convex on the interval $[a,b]$ for any $x_1,x_2,\cdots ,x_n\in [a,b]$, then
$\frac{f(x_1)+f(x_2)+\cdots +f(x_n)}{n}\geq f\left(\frac{x_1+x_2+\cdots +x_n}{n}\right)$.
Equality holds when $x_1=x_2=\cdots =x_n$.
The sign is reversed for a concave function.

For the proof of Jensen's inequality, one can apply mathematical induction and make use of the definition of a convex function:
A function $f$ is convex on the interval $[a,b]$ if for any $x_1,x_2\in [a,b]$,
$tf(x_1)+(1-t)f(x_2)\geq f(tx_1+(1-t)x_2)$ where $t$ is any positive real number smaller then $1$.
The sign is reversed for a concave function.

how to prove the integral form of jensen's inequality?


Sorry if I'm bothering you Asymptote experts by posting too many questions today, but can you use the colors in hexadecimal when filling? If not, is there a list of what colors are programmed into Asymptote? Thanks.

EDIT: I'm probably really annoying everyone who reads my questions (4th one!), but Is it possible to write words vertically as if along the y axis? Thanks.

You could use $ \text{\LaTeX}$ to write words vertically, if that's what you're asking.

You can rotate labels by any angle (though I'm not sure if that's what you are asking):
[asy]size(150);
draw((0,0)--(1,2));
real a=degrees((1,2));
label(rotate(a)*"$\mbox{an interval}$",(0.5,1),NW);[/asy]
As to colors in hexadecimal, Asymptote has rgb() command; only the three intensities should be usual decimals between 0 and 1.

[quote="fedja"]
[code]
size(150);
draw((0,0)--(1,2));
real a=degrees((1,2));
label(rotate(a)*"$\mbox{an interval}$",(0.5,1),NW);
[/code][/quote]

A more elegant solution is
[asy]size(150);
path g=(1,-1)--(3,4);
draw(Label("an interval",Rotate(dir(g))),g);
draw(Label("an interval",Rotate(-dir(g)),align=I*dir(g)),g);[/asy]

[quote="dragon96"]Yes, that was what I was asking.
Looking at your code, the "\mbox{}" is the words it displays, right? And what does the code mean when it says "degrees (1,2)"? Thanks.[/quote]

I'm guessing that degrees(x,y) means $ \tan^{\minus{}1}\frac{y}{x}$ in degrees.


function
trigonometry
inequalities
ratio
calculus
derivative
real analysis

So, I have this problem:
$ \text{Prove that the function }f(x) = x\sin\left( \frac{1}{x}\right) \text{ is uniformly continuous on }\mathbb{R}.$

The textbook offered a convoluted solution, and I came up with a solution of my own, which is much, much shorter. I am still skeptical about my solution, and I would like to see if there are any holes in it.

My solution is hidden below
[hide]Let $ \epsilon > 0$, and $ \delta = \epsilon/2$. Let $ x,y\in\mathbb{R}$. Suppose $ |x-y|<\delta$. Note the inequality

\begin{eqnarray*}|f(x)-f(y)| &=& |x\sin\left( \frac{1}{x}\right)-y\sin\left( \frac{1}{y}\right)|\\ &\le& |x\sin\left( \frac{1}{x}\right)-y\sin\left( \frac{1}{x}\right)+x\sin\left( \frac{1}{y}\right)-y\sin\left( \frac{1}{y}\right)|\\ &=& |x-y||\sin\left( \frac{1}{x}\right)+\sin\left( \frac{1}{y}\right)|\\ &\le& |x-y|(|\sin\left( \frac{1}{x}\right)|+|\sin\left( \frac{1}{y}\right)|) \\ &\le& |x-y|(1+1) \\ &=& 2|x-y| \end{eqnarray*}

Now since $ |x-y|<\delta$ and $ \delta = \epsilon/2$, we have:
$ |x-y|<\epsilon/2$
$ 2|x-y|<\epsilon$

Applying this to the string of inequalities above,
$ |f(x)-f(y)|<\epsilon$,

which proves that $ f$ is uniformly continuous on $ \mathbb{R}$. $ \blacksquare$

The textbook did this:
1. Establish the fact that if $ f$ is a real-valued function that is uniformly continuous on a set $ [k,+\infty)$, then it must be continuous on $ [0,+\infty)$.
2. This reduces the problem to showing that $ f(x) = x\sin\left( \frac{1}{x}\right)$ is uniformly continuous on $ [1,+\infty)$ and on $ (-\infty,-1]$. If that is proven, then since $ f$ is uniformly continuous on $ [0,+\infty)$ and on $ (-\infty,0]$, it must be continuous on $ \mathbb{R}$.
3. The statement in 2 can be proved by noting that $ f(x) = x\sin\left( \frac{1}{x}\right)$ is differentiable (and continuous) on both $ [1,+\infty)$ and on $ (-\infty,-1]$, and $ f'(x)$ is bounded on both sets. Hence, $ f(x)$ is uniformly continuous on those sets.

I like my purely algebraic solution better than this. Hopefully, my solution is correct.[/hide]

The problem with your argument is that it's wrong. You are claiming that $ f$ is Lipschitz. In particular, you are claiming that $ \left|\frac{f(x)-f(y)}{x-y}\right|\le 2.$

Now let $ x=\frac{2}{(2k-1)\pi}$ and $ y=\frac{2}{(2k+1)\pi}.$

With a little algebra you can show that $ \left|\frac{f(x)-f(y)}{x-y}\right|=2k.$

(Or something like that, anyway.) The ratio is not bounded and $ f$ is not Lipschitz.

---

My shorthand thought processes for deciding that it's uniformly convergent: First, is there any problem as $ x\to\infty?$ No, because the derivative gets very small out that way. It is Lipschitz on something like $ [1,\infty).$ Now, what happens as $ x\to0?$ The function has a limit; hence it can be extended to be a continuous function on $ [0,1],$ but then a continuous function on a compact set is uniformly continuous.

I'd write a little more for a formal argument, but this is the gist of it.

A less standard approach: $ f^{3}$ is Lipschitz because its derivative is continuous and bounded [by a direct calculation]. Therefore, $ f=(f^{3})^{1/3}$ is a composition of two uniformly continuous functions. As a bonus we get that $ f$ is Holder continuous.


function
induction
algebra proposed
algebra
functional equation

Set $ y\equal{}0$ then

$ f(x^3)\equal{}xf(x^2)$ , so $ f(y^3)\equal{}yf(y^2)$ , then

$ f(x^3\plus{}y^3)\equal{}xf(x^2)\plus{}yf(y^2)\equal{}f(x^3)\plus{}f(y^3)$ $ \rightarrow$ $ f(x)\plus{}f(y)\equal{}f(x\plus{}y)$

simple induction gives : $ f(x_1\plus{}x_2\plus{}...\plus{}x_n)\equal{}f(x_1)\plus{}f(x_2)\plus{}f(x_3)\plus{}...\plus{}f(x_n)$  so $ \forall \ n\in\mathbb{R}$

then $ f(nx)\equal{}nf(x)$ and thus by setting $ x\equal{}1$ we have $ f(n)\equal{}nf(1)$, since $ f(1)$ is a constant then by assuming $ f(1)\equal{}a$ , gives $ f(n)\equal{}an$ with $ a\in\mathbb{R}$

done

[quote="matrix41"]Set $ y \equal{} 0$ then

$ f(x^3) \equal{} xf(x^2)$ , so $ f(y^3) \equal{} yf(y^2)$ , then

$ f(x^3 \plus{} y^3) \equal{} xf(x^2) \plus{} yf(y^2) \equal{} f(x^3) \plus{} f(y^3)$ $ \rightarrow$ $ f(x) \plus{} f(y) \equal{} f(x \plus{} y)$

simple induction gives : $ f(x_1 \plus{} x_2 \plus{} ... \plus{} x_n) \equal{} f(x_1) \plus{} f(x_2) \plus{} f(x_3) \plus{} ... \plus{} f(x_n)$  so $ \forall \ n\in\mathbb{R}$ then $ f(nx) \equal{} nf(x)$ [/quote]
Why for all $ n \in R$  :?:

[quote="matrix41"]Set $ y \equal{} 0$ then

$ f(x^3) \equal{} xf(x^2)$ , so $ f(y^3) \equal{} yf(y^2)$ , then

$ f(x^3 \plus{} y^3) \equal{} xf(x^2) \plus{} yf(y^2) \equal{} f(x^3) \plus{} f(y^3)$ $ \rightarrow$ $ f(x) \plus{} f(y) \equal{} f(x \plus{} y)$

simple induction gives : $ f(x_1 \plus{} x_2 \plus{} ... \plus{} x_n) \equal{} f(x_1) \plus{} f(x_2) \plus{} f(x_3) \plus{} ... \plus{} f(x_n)$  so $ \forall \ n\in\mathbb{R}$
then $ f(nx) \equal{} nf(x)$ and thus by setting $ x \equal{} 1$ we have $ f(n) \equal{} nf(1)$, since $ f(1)$ is a constant then by assuming $ f(1) \equal{} a$ , gives $ f(n) \equal{} an$ with $ a\in\mathbb{R}$

done[/quote]
you only solve equation on $ N$ not $ R$
We have:$ f(x \plus{} y) \equal{} f(x) \plus{} f(y)$ and $ f(x^3) \equal{} xf(x^2)$,$ (x) \equal{} \minus{} f( \minus{} x)$,$ f(kx) \equal{} kf(x)$ for all $ k \in N$
We have:
 $ f((x \plus{} 1)^3 \plus{} (x \minus{} 1)^3) \equal{} (x \plus{} 1)f(x^2 \plus{} 2x \plus{} 1) \plus{} (x \minus{} 1)f(x^2 \minus{} 2x \plus{} 1) \equal{} 2xf(x^2) \plus{} 2xf(1) \plus{} 4f(x)$
and $ f((x \plus{} 1)^3 \plus{} (x \minus{} 1)^3) \equal{} f(2x^3 \plus{} 6x) \equal{} 2xf(x^2) \plus{} 6f(x)$
So $ f(x) \equal{} xf(1)$ for all $ x \in R$

Sorry there are some mistakes in my solution

Let me write my full solution

First from my first post, we have

$ f(x_1)\plus{}f(x_2)\plus{}...\plus{}f(x_n)\equal{}f(x_1\plus{}x_2\plus{}x_3\plus{}...\plus{}x_n)$ with $ n\in\mathbb{N}$ so $ f(nx)\equal{}nf(x)$ $ \forall n\in\mathbb{N}$

and then by setting $ x\equal{}m\plus{}1$ and $ y\equal{}m\minus{}1$ it gives

$ f((m\plus{}1)^3\plus{}(m\minus{}1)^3)\equal{}f((m^3\plus{}3m^3\plus{}3m\plus{}1)\plus{}(m^3\minus{}3m^3\plus{}3m\minus{}1))\equal{}f(2m^3\plus{}6m)\equal{}f(2m^3)\plus{}f(6m)\equal{}2f(m^3)\plus{}6f(m)$

and

$ f((m\plus{}1)^3\plus{}(m\minus{}1)^3)\equal{}(m\plus{}1)f(m^2\plus{}2x\plus{}1)\plus{}(m\minus{}1)f(x^2\minus{}2x\plus{}1)\equal{}(m\plus{}1)\left(f(m^2)\plus{}f(2m)\plus{}f(1)\right)\plus{}(m\minus{}1)\left(f(m^2)\plus{}f(\minus{}2m)\plus{}f(1)\right)\equal{}2mf(m^2)\plus{}4f(m)\plus{}2mf(1)$

since $ 2mf(m^2)\equal{}2f(m^3)$ , so $ f((m\plus{}1)^3\plus{}(m\minus{}1)^3)\equal{}2mf(m^2)\plus{}4f(m)\plus{}2mf(1)\equal{}2f(m^3)\plus{}4f(m)\plus{}2mf(1)$

$ 2f(m^3)\plus{}6f(m)\equal{}f((m\plus{}1)^3\plus{}(m\minus{}1)^3)\equal{}2f(m^3)\plus{}4f(m)\plus{}2mf(1)$

$ 2f(m)\equal{}2mf(1)$ $ \rightarrow$ $ f(m)\equal{}mf(1)$ $ \forall m\in\mathbb{R}$

please check....

EDITED : Sorry I didn't know that my solution is similar to math10's solution  :oops:

not so hard.
let $y=0$,then
$f(x^3)=xf(x^2)$
so $f(x^3+y^3)=f(x^3)+f(y^3)$
hence f satisfies Cauchy's  function,so for rational x,$f(x)=x$
hence $f(1)=1$
by letting $x=x+1$ we get
$f((x+1)^3)=(x+1)f((x+1)^2)$
hence $2f(x^2)=(2x-1)f(x)+x$
let $x=x+1$
we get $2(f(x^2)+2f(x)+1)=(2x+1)(f(x)+1)+x+1$
hence $f(x)=x$.

[quote="pco"][quote="littletush"] ... hence f satisfies Cauchy's  function,[/quote]Right
[quote="littletush"]so for rational x,$f(x)=x$[/quote]Wrong : $f(x)=ax$[/quote]
oh gush!such a terrible mistake!
a can be any real number.

It is easy to show that ∃$a\in \mathbb R$ s.t. $f(x)=ax(\forall x\in \mathbb Q)$.

If we show that $f$ is
-continuous at some point
-monotonous
-either upperbounded or lowerbounded on some open interval

$f(x)=ax(\forall x\in \mathbb R)$ :P

Anyone has idea? :?

[quote=Raja Oktovin]Find all functions $ f: \mathbb{R} \rightarrow \mathbb{R}$ satisfying \[ f(x^3\plus{}y^3)\equal{}xf(x^2)\plus{}yf(y^2)\] for all real numbers $ x$ and $ y$.
[i]Hery Susanto, Malang[/i][/quote]

Let $P(x,y)$ be the assertion $f(x^3+y^3)=xf(x^2)+yf(y^2)$
Let $a=f(1)$

$P(0,0)$ $\implies$ $f(0)=0$
$P(x,0)$ $\implies$ $f(x^3)=xf(x^2)$
And so $f(x^3+y^3)=f(x^3)+f(y^3)$ and so $f(x)$ is additive.

So $f(px)=pf(x)$ $\forall x$ and $\forall p\in\mathbb Q$

Let $x\in\mathbb R$ and $k\in\mathbb Q$
$P(x+k,0)$ $\implies$ $f(x^3+3kx^2+3k^2x+k^3)=(x+k)f(x^2+2kx+k^2)$

Which may be written $k^2(f(x)-ax)+2k(f(x^2)-xf(x))=0$

Considering this as a polynomial in $k$ with infinitely many roots (any rational), we get thet it must be the zero polynomial and so, looking at coefficient of $k^2$ :

$\boxed{f(x)=ax\text{  }\forall x}$ which indeed is a solution, whatever is $a\in\mathbb R$

@pco,@anhtaitran
What a nice solution! :w00t: Are you a FE master? :lol:

[quote=Evenprime123][quote=pco]
And so $f(x^3+y^3)=f(x^3)+f(y^3)$ and so $f(x)$ is additive.

So $f(px)=pf(x)$ $\forall x$ and $\forall p\in\mathbb Q$
[/quote]

How do I conclude this? Induction would work on \(\mathbb N \) but what can I do here?[/quote]
You should consider this as a well-known property of additive functions.

If you want to prove it :
$f(2x)=f(x)+f(x)=2f(x)$
$f(3x)=f(2x)+f(x)=3f(x)$
And, with induction : $f(nx)=nf(x)$ $\forall x$, $\forall n\in\mathbb N$

So $f(x)=f(q\frac xq)=qf(\frac xq)$ and so $f(\frac xq)=\frac 1qf(x)$ $\forall x$, $\forall q\in\mathbb N$

So $f(\frac pqx)=pf(\frac xq)=\frac pqf(x)$ and so $f(px)=pf(x)$ $\forall x$, $\forall p\in\mathbb Q^+$

It remains to remember that $f(-x)=-f(x)$ and $f(0)=0$ and so
$f(px)=pf(x)$ $\forall x$, $\forall p\in\mathbb Q$

[quote=GeronimoStilton]Some progress:
...
... so I can't finish the problem.[/quote]
Sorry, but what is the interest of this post ?
Just publicly claim that you are working on this problem ? And what about your progress about your sister's garden ? and what is the last film you liked ?
Just request for some help ? : read the thread ! there is already a full solution (see post #10)
Just bring some new informations to the community ? but this contribution already has been given at least thrice in the current thread (and btw is the beginning of the full solution in the post #10)

This is a folklore:
$\bigstar \color{blue}{\textit{\textbf{ANS:}}}$ $f(x)=cx \quad x\in \mathbb{R}$ where $c\in \mathbb{R}$.
$\spadesuit \color{red}{\textit{\textbf{Proof:}}}$ It's easy to see that this is a solution to the given FE. Let $P(x,y)$ denote the given assertion, \[P(x,-x): f(0)=0\] \[P(x,0): f(x^3)=xf(x^2).\] So, let $u=x^3, v=y^3$, $f(u+v)=f(x^3+y^3)=xf(x^2)+yf(y^2)=f(x^3)+f(y^3)=f(u)+f(v)$ and $f$ is additive. We use a standard trick: \[P(x+1,x-1): \boxed{f(x)=f(1)x \quad \forall x\in \mathbb{R}}\] as many terms cancel nicely due to additivity and it yields the desired result. $\quad \blacksquare$

[quote=Raja Oktovin]Find all functions $ f: \mathbb{R} \rightarrow \mathbb{R}$ satisfying \[ f(x^3\plus{}y^3)\equal{}xf(x^2)\plus{}yf(y^2)\] for all real numbers $ x$ and $ y$.
[i]Hery Susanto, Malang[/i][/quote]
$\color{blue} \boxed{\textbf{Answer: f(x)=cx}}$
$\color{blue} \boxed{\textbf{Proof:}}$
$\color{blue} \rule{24cm}{0.3pt}$
$$f(x^3+y^3)=xf(x^2)+yf(y^2)...(\alpha)$$
In $(\alpha) y=0:$
$$\Rightarrow f(x^3)=xf(x^2)...(\beta)$$
$(\beta)$ in $(\alpha):$
$$\Rightarrow f(x^3+y^3)=f(x^3)+f(y^3)$$
$$\Rightarrow f(x+y)=f(x)+f(y)...(I)$$
In $(\beta) x=x+1:$
$$\Rightarrow f(x^3+3x^2+3x+1)=(x+1)f(x^2+2x+1)$$
By $(I):$
$$\Rightarrow f(x^3)+f(3x^2)+f(3x)+f(1)=xf(x^2)+xf(2x)+xf(1)+f(x^2)+f(2x)+f(1)$$
$$\Rightarrow f(x)=xf(1)$$
$$\Rightarrow \boxed{\textbf{f(x)=cx}}_\blacksquare$$
$\color{blue} \rule{24cm}{0.3pt}$

[quote=F10tothepowerof34]This problem is very similar to [url=https://artofproblemsolving.com/community/c6h150112p847891]Macedonian Mathematical Olympiad 2007 P4[/url][/quote]
It's the same problem...


algebra
polynomial
linear algebra
matrix
linear algebra unsolved

We know that $\exp(\mathcal{M}_{n}(\mathbb{C}))=\mbox{GL}_{n}(\mathbb{C})$.
It was shown by alekk that $\exp(\mathcal{M}_{n}(\mathbb{R}))=\{ M^{2}, M \in \mbox{GL}_{n}(\mathbb{R})\}$, http://www.artofproblemsolving.com/Forum/viewtopic.php?highlight=polynomial&t=43500.

So, what can we say about $\exp(\mathcal{M}_{n}(\mathbb{Q}))$, or $\exp(\mathcal{M}_{n}(\mathbb{F}))$, where $\mathbb{F}$ is a field different than $\mathbb{C}$ or $\mathbb{R}$, and not algebraically closed?

We shouldn't be talking about the exponential in a field that isn't complete- the partial sums of the defining power series are usually Cauchy, but there's no reason to expect convergence without completeness.

$\mathbb{Q}_{p}$ might be interesting. The exponential has finite radius of convergence there, which makes things really weird.

jmerry,
I agree with your comment, however $\exp (\mathcal{M}_{n}(\mathbb{Q}))$ is a subset of $\mathcal{M}_{n}(\mathbb{R})$ that one might be able to define more precisely.

Easy remark: if $U=\{ M^{2}, M \in \mbox{GL}_{n}(\mathbb{R})\}$ and $V=\exp (\mathcal{M}_{n}(\mathbb{Q}))$ then $V$ is a denumerable dense subset of $U$.
More difficult: if $A,B\in\mathcal{M}_{n}(\mathbb{Q})$ then $e^{A}e^{B}=e^{B}e^{A}$ $\Longleftrightarrow$ $AB=BA$; it's a Wermuth's result.
First idea of the proof: if $u,v$ are 2 distinct $A$ or $B$'s eigenvalues then $u-v$ is algebraic over $\mathbb{Q}$ and $u-v\notin 2i\pi\mathbb{Z^{*}}$.
Second idea: if $A\in\mathcal{M}_{n}(\mathbb{Q})$ then $A$ is a polynomial in $e^{A}$.
In particular if $A,B\in\mathcal{M}_{n}(\mathbb{Q})$ then $e^{A}=e^{B}$ implies $AB=BA$ and $spectrum(A)=spectrum(B)$ but the converse is false: take for example $0$ and $N$ a nilpotent matrix over $\mathbb{Q}$.


Prove that $ \left(1\minus{}x\right)\sqrt{1\plus{}3x\minus{}4x^3}\ge\frac{1}{12}$ if $ 0\le x \le\frac{1}{2}$.

$ (1 \minus{} x)\sqrt {1 \plus{} 3x \minus{} 4x^2} \equal{} (1 \minus{} x)\sqrt {(1 \minus{} x)(1 \plus{} 2x)^2} \equal{} (1 \plus{} 2x)(1 \minus{} x)^{\frac {3}{2}}$
Let $ f(x) \equal{} (1 \plus{} 2x)(1 \minus{} x)^{\frac {3}{2}}$. Then, for $ x\le 1$, have:
$ f'(x) \equal{} (1 \plus{} 2x)\frac {3}{2}(1 \minus{} x)^{\frac {1}{2}} \plus{} (1 \minus{} x)^{\frac {3}{2}}*2 \equal{} (1 \minus{} x)^{\frac{1}{2}}(\frac {3}{2}(1 \plus{} 2x) \plus{} 2(1 \minus{} x))$
If $ x\in [0,\frac {1}{2}]$ have $ (1 \minus{} x)^{\frac {1}{2}} > 0$ then:
$ f'(x) \equal{} (1 \minus{} x)^{\frac {1}{2}}(\frac {3}{2}(1 \plus{} 2x) \plus{} 2(1 \minus{} x)) > \frac {3}{2}(1 \plus{} 2x) \plus{} 2(1 \minus{} x) \equal{} \frac {7}{2} \minus{} x > 0$
Therefore, $ f(x)$ is strictly increasing on $ (0,\frac {1}{2})$ hence for any $ x\in [0,\frac {1}{2}]$ have $ \left(1 \minus{} x\right)\sqrt {1 \plus{} 3x \minus{} 4x^3} \equal{} f(x) > f(0) \equal{} \frac {1}{2}$ and the result follows.
Maybe I made a calculation mistake somewhere. :maybe:


algorithm
number theory
greatest common divisor
number theory unsolved

$m, n$ are relatively prime. We have three jugs which contain $m$, $n$ and $m+n$ liters. Initially the largest jug is full of water. Show that for any $k$ in $\{1, 2, ... , m+n\}$ we can get exactly $k$ liters into one of the jugs.

Suppose $m>n$.

Key fact from number theory: the sequence $n,2n...mn$ is a permutation of $1,2,3..m$ modulo $m$.

Now fill up the $n$ bucket. Pour contents from $n$ bucket to $m$ bucket. Repeat until it is no longer possible.

Because it is no longer possible then that means that one of the following happens:

(1) We cannot pour $n$ litres into the $m$ bucket without making it overflow
(2) We don't have enough water in the $m+n$ bucket to fill up the $n$ bucket.

However it is easy to see that (2) cannot happen as we have $m+n$ litres in total, at most $m$ in the $m$ bucket, $0$ in the $n$ bucket and hence at least $n$ in the big bucket. Hence we can fill up the $n$ bucket and (1) occurs. So what we can do is pour in just enough to fill up the $m$ bucket, hence we have $r$ litres in the $n$ bucket, we can now pour in the contents in the $m$ bucket into the big bucket, and pour in the $r$ litres into the $m$ bucket.

Now notice that $r \equiv in \mod m$ where $i$ is the number of times we poured something from the $n$ bucket into the $m$ bucket so far.

Now we can keep continuing this process and we see that at the $ith$ step the amount of water in the $m$ bucket is congruent to $in \mod m$ Hence using the key fact above we have proven that for any $k$ in $\{1,2,3...m\}$ we can have $k$ litres in the $m$ bucket. Now if $m<k\leq m+n$ then $0 < k-n \leq m$. So perform the algorithm such that we have $k-n$ litres in the $m$ bucket. Now fill up the $n$ bucket and empty the $m+n$ bucket .Now add the contents from the $n$ and $m$ bucket together in the $m+n$ bucket.

If$(m,n)>1$ the statement becomes false;
If $(m,n)=1$ we can pour water following Euclid's algorithm for GCD and we'll have 1liter of water.
Now we repeat the procedure for k times.


Let $ t \ge 3$  be a given real number and assume that the polynomial $ f(x)$ satisfies $|f(k)\minus{}t^k|<1$, for $ k\equal{}0,1,2,\ldots ,n$. Prove that the degree of $f(x)$ is at least $n$.

[quote="TTsphn"]A good problem .It can be prove by Lagrange with n nut $ 1,2,...,n$ if deg P<n.[/quote]

Please explain more. Or provide a more elementary solution.

Suppose $ f$ is a polynomial of degree less than $ n$. The polynomial
\[ \sum_{k\equal{}0}^n f(k)\prod_{j\neq k} \frac{x\minus{}j}{k\minus{}j}\]
is the unique polynomial of degree [i]less than or equal to[/i] $ n$ given the values of $ f(k)$ for $ k\equal{}0,1,\cdots, n$. So that polynomial must be $ f$ and the $ x^n$ term must be 0. Therefore,
\[ 0\equal{}\sum_{k\equal{}0}^n \frac{f(k)}{\prod_{j\neq k} (k\minus{}j)}\equal{}\sum_{k\equal{}0}^n \frac{(\minus{}1)^{n\minus{}k}}{k!(n\minus{}k)!}f(k)\equal{}\frac{1}{n!}\sum_{k\equal{}0}^n (\minus{}1)^{n\minus{}k}\binom{n}{k}f(k)\]
But we have $ t^k\minus{}1<f(k)<t^k\plus{}1$ for all $ k$, so that
\[ 0>(t^n\minus{}1)\binom{n}{n}\plus{}(t^{n\minus{}2}\minus{}1)\binom{n}{n\minus{}2}\plus{}\cdots\]
\[ \minus{}(t^{n\minus{}1}\plus{}1)\binom{n}{n\minus{}1}\minus{}(t^{n\minus{}3}\plus{}1)\binom{n}{n\minus{}3}\minus{}\cdots\]
\[ \equal{}(t\minus{}1)^n\minus{}2^n\geq 0\]
a contradiction. So $ f$ must have degree at least $ n$.

[quote="scorpius119"] The polynomial
\[ \sum_{k \equal{} 0}^n f(k)\prod_{j\neq k} \frac {x \minus{} j}{k \minus{} j}
\]
is the unique polynomial of degree [i]less than or equal to[/i] $ n$ given the values of $ f(k)$ for $ k \equal{} 0,1,\cdots, n$. [/quote]

What do you mean here?  :huh:

Suppose $ P(x)\equal{}\sum_{k\equal{}0}^n f(k)\prod_{j\neq k} \frac{x\minus{}j}{k\minus{}j}$. Observe that each of the products $ \prod_{j\neq k} \frac{x\minus{}j}{k\minus{}j}$ have degree $ n$, so $ P$ has degree at most $ n$. Also, $ P(0)\equal{}f(0)$ because the product in the 0th term in the sum is $ \frac{\minus{}1}{\minus{}1}\cdot \frac{\minus{}2}{\minus{}2}\cdot \cdots \frac{\minus{}n}{\minus{}n}\equal{}1$ and the product in the $ k$th term for $ k\neq 0$ is $ \frac{0}{\minus{}k}\cdot \text{whatever}\equal{}0$.

In a similar way, $ P(1)\equal{}f(1),P(2)\equal{}f(2),\cdots P(n)\equal{}f(n)$. If $ z(x)\equal{}P(x)\minus{}f(x)$, then $ z$ has degree at most $ n$ but $ n\plus{}1$ roots, so must be the zero polynomial, giving $ f(x)\equal{}P(x)$. Of course, $ P$ usually will have degree $ n$, so the condition that $ f$ has degree strictly less than $ n$ requires the $ x^n$ coefficient of $ f$ to be 0.

Define the polynomial $ \binom{x}{n}: \equal{}{x(x\minus{}1)\cdots(x\minus{}n\plus{}1)\over n!}$ for $ n\in\mathbb{N}$ and $ \binom{x}{0}\equiv 1$.

Then $ f_n(x)\equal{}2^n\binom{x}{n\minus{}1}\plus{}2^{n\minus{}2}\binom{x}{n\minus{}3}\plus{}\cdots\equal{}\sum_{i\equal{}0}^n (1\minus{}(\minus{}1)^{n\minus{}i})2^i\binom{x}{i}$
has degree $ n\minus{}1$ and leading coefficient $ {2^n\over (n\minus{}1)!}$ for all $ n\in\mathbb{N}$,
and for all $ k\equal{}0,1,\ldots,n$ we have
$ f_n(k)\equal{}\sum_{i\equal{}0}^k (1\minus{}(\minus{}1)^{n\minus{}i})2^i\binom{k}{i}\equal{}(2\plus{}1)^k\minus{}(2\minus{}1)^k$.
So $ f_n(k)\minus{}3^k\equal{}(\minus{}1)^{k\plus{}1}$ and $ |f_n(k)\minus{}3^k|\equal{}1$ for all $ k\equal{}0,1,\ldots ,n$.

scorpius119's argument shows, that this is in fact the only polynomial $ f$ of degree $ <n$
with $ |f(k)\minus{}t^k|\le 1$ for all $ k\equal{}0,1,\ldots,n$ and some $ t\ge 3$.
Nice!   :D

[i] You are really intelligent  Scorpius119

  So wonderful

   Nice and  short solution[/i] :lol:


[hide="In the reals"] We have $y < \log_{3}7 < 2$ and $x < \log_{3}11 < 3$.  In particular, we have the solution $\boxed{ (2, 1) }$.

Clearly if we have a solution for $x > 2, y < 1$ then $3^{x}$ increases by more than $2^{x}$, but $3^{y}$ decreases by more than $2^{y}$, so equality can no longer occur.  A similar argument for $x < 2$ suffices, I think, to show the nonexistence of any more real solutions. [/hide]


If $a,b,c$ are positive real numbers such that $a+b+c = 1$, prove that \[ (1+a)(1+b)(1+c) \geq 8 (1-a)(1-b)(1-c) . \]

Taking a+b=x,b+c=y and c+a=z,we get (x+y)(y+z)(z+x)>=8xyz
Apply A-M,G-M to get
x+y>=2[xy]^1/2
y+z>=2[yz}^1/2
z+x>=2[zx]^1/2
Multiply these to get the result.(note that x,y,z are positive real numbers)

[quote] i did not get the proof [color=#80BF00][color=#FFBFBF][size=200] :wink:  :!: [/size][/color][/color][/quote]

Taking $a+b=x$,$b+c=y$ and $c+a=z$,we get $(x+y)(y+z)(z+x)$>$=8xyz$
Apply A-M,G-M to get
$x+y$>=2$[xy]^{1/2}$
$y+z$>=2$[yz]^{1/2}$
$z+x$>=2$[zx]^{1/2}$
Multiply these to get the result.(note that x,y,z are positive real numbers)

The inequality is equivalent to

$\prod_{cyc}(2a+b+c)\geq 8\prod_{cyc}(b+c)$

Expanding this, we get

$2(\sum_{cyc}a^3)\geq \sum_{cyc}a^2b+\sum_{cyc}a^2c$

This holds by Muirhead inequality :D

simplification leads to
     2 + 9abc >= 7( ab +bc + ca )
->  2((a + b + c )^3 ) +9abc >= 7( ab +bc + ca )( a + b + c )
further simplification gives
      2( a^3 + b^3 + c^3 ) >= ab( a+ b ) + bc( b+ c ) + ca( c + a )
 now by AM>=GM
     a^2 + b^2 >= 2ab
->  a^2 + b^2 - ab >= ab
->  (a^2 + b^2 - ab)( a+ b ) >= ab( a + b )
-> a^3 + b^3 >= ab( a + b )
similarly
b^3 + c^3 >= bc( b + c )
c^3 + a^3 >= ca( c + a )
adding the three equations give us the desired result

How to overkill? Let $$\forall_{x\in(0;1)}f(x)=\ln\frac{1+x}{1-x}$$
Then
$$f''(x)=\frac{ 4 x}{(x^2 - 1)^2}>0$$
Hence $f(x)$ is convex and by Jensen's theorem we get
$$f(a)+f(b)+f(c)\ge3f\left(\frac12\right)$$
which is equivalent to our inequality.


Euler
LaTeX
number theory proposed
number theory

let be $a,n,m\in\mathbb{N}$
If $n|m$ and $a$ is a primitive root of $m$, it is a primitive root of $n$.?

I think it is true, but I had some problems  in proing it.
It's equivalent to proof that if $(a,m)=1$ exists $b=a\mod m$  such that $(a,n)=1$

WELL, i think the difficult case is when m=p^l and show that if g is a primitive root mod m then it is also a primitive root mod n=p^j l>j.  Supose h is the smallest integer such that g^h=1(modn) then use the lemma: if a=b(modp^a) then a^p=b^p(modp^(a+1)) and use it several times to get:

g^h*p^(l-j)=1(mod m) then (p-1)p^(l-1) divides h*p^(l-j) from where we get that h>=(p-1)p^(j-1) and clearly h=(p-1)p^(j-1) because of euler theorem.

the other cases, when n=2p^l are handled in the same way or even easier in some cases.

The rest are details.

BTW sorry, i havent learn latex

You're asking two different questions, hcast.
Primitive roots mod $k$ exist if and only if the multiplicative group of integers mod $k$ is cyclic. This is true for all primes, but not all integers- it fails for any integer divisible by two distinct odd primes, or one divisible by $4p$ for some prime $p$. The integers mod 8 fail here, as the square of any odd integer is 1 (mod 8). Therefore, for $a=1,m=2,n=8$, your conjecture is trivially false. $a=2,m=3,n=15$ would cause the same problem.

On the other hand, your second question is quite obviously true. The ring of integers mod $n$ is the image of the ring of integers mod $m$ under the homomorphism $(a \mod m) \to (a \mod n)$, so the invertible elements of the second ring are mapped surjectively to the invertible elements of the first.

Thanks for your answers ....
I was wondering to prove it without using the fact the  only numbers that have primitive roots are $2,4,p^\alpha,p^{2\alpha}$ are the only naturals that have primitive roots. If anybody knows how, please let me know.

In other hand I said the fact that the natural morfism $\mathbb{Z}_n\longrightarrow\mathbb{Z}_m$ sends suryectivaly the inversible clases is equivalent that a primitive root of $\mathbb{Z}_n$ is a primitive root of $\mathbb{Z}_m$ (Because if $a$ generates $\mathbb{Z}^*_n$ it's image gernerates the image of $\mathbb{Z}^*_n$,  $\mathbb{Z}^*_m$ )
So its not trivial as it seems.

Sorry for the confusion- I accidentally interchanged $m$ and $n$ (now fixed) in my second answer. The direction you get is the useless one; that if $a$ is a primitive root mod $m$ it is also a primitive root mod $n$.

eh, numbers that have primitive roots are those of the form 2,4,p^a or 2p^a you forgot the last one. [quote]   [/quote]

jmerry:       Don't worry, it happened to me too..... ;)

Pascual: You are right, I wrote $p^{2\alpha}$ when I should write $2p^\alpha$


given that
$\cos a+\cos b=\sqrt{\frac{1}{2}}$
$\sin a+\sin b=\sqrt{\frac{3}{2}}$
with $0\leq a ,b\leq pi$
find the value of
$a+b$

[hide="Maybe..."]
Multiply the two together?[/hide]

[hide="hint"]$\cos \alpha+\cos \beta=2\cos\frac{\alpha+\beta}{2}\cos\frac{\alpha-\beta}{2}, \ \ \sin \alpha+\sin \beta= ...$[/hide]

[hide="answer"]$\frac{2\pi}{3}$[/hide]

[hide="remark"]It's possible to find not only the sum but both it's members:
$\alpha = \frac{\pi}{3}\pm \frac{\pi}{4}, \ \ \beta=\frac{\pi}{3}\mp \frac{\pi}{4}$[/hide]

Square both equations and add them to get $\cos a\cos b+\sin a\sin b=0\implies a-b=\frac{\pi}{2}$. Substitute $a=\frac{\pi}{2}+b$ into the original equations to get $\cos b-\sin b=\frac{\sqrt{2}}{2}$ and $\cos b+\sin b=\sqrt{\frac{3}{2}}$.  Add them and solve for $\cos b$ to get $\cos b=\frac{\sqrt{6}+\sqrt{2}}{4}=\cos\left(\frac{\pi}{4}-\frac{\pi}{6}\right)=\cos\frac{\pi}{12}$.  Solve for $a$ and add $b=\frac{\pi}{12}$ to get $a+b=\frac{2\pi}{3}$, as required.


geometry
circumcircle
trapezoid
geometry solved

But it's [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=29893]this[/url] problem in disguise! :) Actually, it's a particular case of it.

Let $U=BC'\cap CA,\ V=CB'\cap AB$. We get $\angle BUC=\angle UCC'+\angle UC'C=2\angle BAC$. In the same way, we find $\angle BVC=2\angle BAC$. It means that $U,V$ are the intersections of the circle $(BOC)$ with $CA,AB$ respectively.

Now, since $AV=VC$ (quick angle chase), the perpendicular through $V$ to $CA$ passes through $O$, i.e. $VO\perp CA$. In the same way, $UO\perp AB$, so $O$ is the orthocenter of $AUV$. $H$ is the orthocenter of $ABC$, and now the conclusion follows from that problem from ISL which I cited in the thread mentioned above, which was equivalent to the problem you posted in the respective thread.

[quote="Stun"]Given the triangle $ABC$ with the circumcircle $(O)$ and orthocenter $H$. $B'$ and $C'$ are two points on (O) such that $BB'//AC$ and $CC'//AB$
$BC'\cap CB'\equiv D$ . Prove that D,H,O are collinear.[/quote]

This is also another problem in disguise: http://www.mathlinks.ro/Forum/viewtopic.php?t=25859 .

In fact, the quadrilateral ABC'C is a trapezoid (since CC' || AB) and it is cyclic (since the point C' lies on the circumcircle of triangle ABC). A cyclic trapezoid must be isosceles; thus, the trapezoid ABC'C is isosceles, and it follows that < C'BA = < BAC. In other words, < DBA = < BAC. Similarly, the trapezoid ACB'B is isosceles, and thus, < BAC = < ACB', what is equivalent to < BAC = < ACD. Together with < DBA = < BAC, this yields < DBA = < BAC = < ACD. Now, it remains to apply the problem discussed in http://www.mathlinks.ro/Forum/viewtopic.php?t=25859 to the quadrilateral BACD (not ABCD).

  Darij


Well, after having solved a past olympiad problem(it wasn't very difficult) i thought that it would be very interesting to change one of the conditions given as in this new version that follows seems extremely difficult. I haven't solved it yet and i think that it can't be solved without using some brute force. Anyway here is the new version and i'd like any solutions.

There are $ 10001$ students at an university. Some students join together to form several clubs (a student may belong to different clubs). Some clubs join together to form several societies (a club may belong to different societies). There is a total of $ k$ societies. Suppose that the following conditions hold:

i.) Each pair of students are in exactly one club.

ii.) For each student and each society, the student is in exactly one club of the society.

iii.) Each club has an odd number of students. In addition, a club with $ 2m \plus{} 7$ students ($ m$ is a positive integer) is
in exactly $ m$ societies.

Find all possible values of $ k$.

In the original problem instead of $ 2m \plus{} 7$ it was $ 2m \plus{} 1$, which makes the problem relatively easy.


Hi,

My son is just starting out. Is there a place I can find countdown round questions & answers from past years?

Any help/pointers is greatly appreciated!

Thanks!

For The Win (accessible on the side of the AoPS page) contains many countdown style problems. There are also answers to the problems. You can play head-to-head with other AoPSers and guests.

For the Win is good, but a lot of the problems that they use are MC target round, team round, AMC 10, and AMC 12 problems, not actual countdown round problems. If you want the real thing, you can get a few problems on the mc website at

https://mathcounts.org/Page.aspx?pid=295

Also, you can buy a CD with the countdown problems from a previous year, and it looks exactly like what you see in an actual countdown round.

 I hope this helps!


Hi there.  I'm something of a forum lurker, hiding in the shadows and coming out only occasionally.  In any case, there's my introduction, on to my question.

I'm working on finishing off round 3, and, for the first time, I gave equations numbers and later referenced them in two separate problems.  However, since the USAMTS solutions are compiled in a single file, let's suppose that problem 50 has equations in it that I label (1) and (2).  Problem 58 has equations that I also wish to label (1) and (2).  However, when I compile, Problem 58 comes out with equations (3) and (4) instead of (1) and (2).  Is there any way to avoid this?  I'm using \ref, so it isn't a problem for me that the numbers change as I add solutions, but it would be somewhat odd for a grader, if they see equation (3), and wonder if they missed equation (1) somehow (though I'm sure they would figure out what happened quickly, or maybe are even used to such oddities).  So, my question is, can I reset the indexing at an arbitrary point mid-latex document, or work around having borked equation numbers in some other way?  Either links to documentation or explanations would be appreciated.  Thanks in advance.

In any case, since I should close with something, I look forward to seeing the solutions for a couple of the problems this round, since some of mine are particularly inelegant.  Good luck all, let's get some neat proofs for slack-jawed amazement in this round.

My advice: don't worry about it.  We're used to seeing later problems start with higher equation numbers.

However, if you do wish to reset the equation number, the command is
\setcounter{equation}{1}

Thanks much.  I usually don't care about presentation at all, but after you've spent 10+ hours solving problems and typing up solutions, it's nice to be able to look at perfect LaTeX ;).


It is from Russian MO 2007 and this problem was posted by N.T.TUAN, [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=912962#912962]here[/url]


Zach Abel
Zarathustra Brady
Ryan Ko
Yi Sun
Arnav Tripathy
Alex Zhai

Can Someone send TST 2006 problems of USA?

[quote="orl"][quote="José"]Are all of them new or they've already gone??[/quote]

It is a pretty smart trick to increase one's post count by asking questions all the time which can be figured out easily by searching them on the web. Look [url=http://www.unl.edu/amc/e-exams/e9-imo/imoteamrecord.html]here,[/url] [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=256848#p256848]there[/url] or [url=http://www.mathlinks.ro/Forum/viewtopic.php?highlight=eric+price&t=40906]in last year's AMC thread.[/url][/quote]

orl is keepin' it real :cool:

good luck to all the USA IMO participants :)

[quote="amir2"][quote="Orl"]It is a pretty smart trick to increase one's post count by asking questions all the time which can be figured out easily by searching them on the web[/quote]

There are smarter tricks too. :D[/quote]

I guess you're right! ;)

[quote="José"][quote="orl"][quote="José"]Are all of them new or they've already gone??[/quote]

It is a pretty smart trick to increase one's post count by asking questions all the time which can be figured out easily by searching them on the web. Look [url=http://www.unl.edu/amc/e-exams/e9-imo/imoteamrecord.html]here,[/url] [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=256848#p256848]there[/url] or [url=http://www.mathlinks.ro/Forum/viewtopic.php?highlight=eric+price&t=40906]in last year's AMC thread.[/url][/quote]

You're wrong orl... I did it because, when you generally post a team, you put their past competences but not this time, but it seemed strange to me that the 6 competitors were new[/quote]

The point remains the same - use google rather than make meaningless posts.

[quote="José"]

You're wrong orl... [/quote]

WTF, HOW IS THIS SENTENCE POSSIBLE?

[quote="MysticTerminator"]Zach Abel
Zarathustra Brady
Ryan Ko
Yi Sun
[b]Arnav Tripathy[/b]
Alex Zhai[/quote]That's self-explanatory, because ... he is our favorite [b]MysticTerminator[/b] !!!
Good job and may the math be with you :D  :starwars:


Let $ a;b;c;d;r;s \in Z^\plus{}$ such that $ rab\equal{}scd$
Prove that:
$ M\equal{}r(a^2\plus{}b^2)\plus{}s(c^2\plus{}d^2)$ is composite

clearly, if $ \gcd(r,s) > 1$, the conclusion is immediate. so assume that $ \gcd(r,s) \equal{} 1$. since $ \frac {r}{s} \equal{} \frac {cd}{ab}$, it then follows that $ cd \equal{} rk$, $ ab \equal{} sk$, for some $ k\in \mathbb{N}$. we now write

$ M \equal{} \frac {cd}{ab}s(a^2 \plus{} b^2) \plus{} s(c^2 \plus{} d^2) \equal{} \frac {s(cd(a^2 \plus{} b^2) \plus{} ab(c^2 \plus{} d^2))}{ab} \equal{}$

$ \frac {s(a^2cd \plus{} b^2cd \plus{} abc^2 \plus{} abd^2)}{ab} \equal{} \frac {s(ac \plus{} bd)(ad \plus{} bc)}{ab} \equal{} \frac {(ac \plus{} bd)(ad \plus{} bc)}{k}$ (*)

note that by AM-GM, $ ac \plus{} bd\geq 2\sqrt {acbd} \equal{} 2k\sqrt {rs} \geq 2k$, and likewise, $ ad \plus{} bc\geq 2k$. since $ M$ is an integer, $ \frac {(ac \plus{} bd)(ad \plus{} bc)}{k}$ must be an integer, so the factorization (*) will produce a factorization of $ M$ where each factor is at least $ 2$. hence $ M$ is composite.

[hide]
The condition implies
\[ Mab\equal{}s(cd(a^2\plus{}b^2)\plus{}ab(c^2\plus{}d^2))\equal{}s(a^2cd\plus{}ab(c^2\plus{}d^2)\plus{}b^2cd)\]
\[ \equal{}s(ac\plus{}bd)(ad\plus{}bc)\]
Now if $ M$ were prime, $ M$ would divide one of $ s,ac\plus{}bd,ad\plus{}bc$. But clearly $ M>s$, and also
\[ M\geq a^2\plus{}b^2\plus{}c^2\plus{}d^2\geq 2(ac\plus{}bd),2(ad\plus{}bc)\]
so $ M$ does not divide any factor. So $ M$ composite.
[/hide]


geometry
3D geometry
sphere
LaTeX
calculus
integration
number theory

6 spheres (A, B, C, D, E, F) as follows:
A has radius 3
B and C have radius 2
D, E, and F have radius 1
D and F are internally tangent to A at points D' and F', respectively such that D'F' = 6
D and F are externally tangent to E
D and E are internally tangent to B
E and F are internally tangent to C
Call X and Y the region with the following boundaries:
A point in region X lies inside sphere A but not in B or C
A point in region Y lies in either B or C but not both, unless it lies in E
A point in region Y does not lie in D or F
If the sums of the volumes of regions X and Y can be expressed as (m*pi)/n
where M and N are relatively prime integers
find the remainder when M+N is divided by 1000

 I don't think M+N exceeds 1000. Not in my answer, anyway. But I think my answer is wrong.

working on solution...
how do you embed latex?
I'm new to this computer stuff and need to figure out how to put it into a reply
sounds dumb
I know
computers aren't really my thing

Embeding latex is simple! Just put dollar signs around the math. So puting them around x=5+5*y^3 makes $x=5+5*y^3$. Some special commands you might want to know are the fraction, \frac{y}{x} makes $\frac{y}{x}$ and the 'implies' arrow sign, so x=5+5 \rightarrow x=10 makes $x=5+5 \rightarrow x=10$. Latex also doesn't use spaces, so $don't put them around writing$.

ok.. we have to find $A-(B\cap C)+E-D-F$ (not necessarily the correct notation)
how would we do this without calculus?

[hide="calculus"]
$\displaystyle A=\frac{4}{3}\pi (3^3)=36\pi\\ E=D=F=\frac{4}{3}\pi (1^3)=\frac{4}{3}\pi$

\begin{eqnarray*} B \cap C&=&2\int_1^2{\pi r^2}dx\\ &=&2\int_1^2{\pi (4-x^2)}dx\\ &=&\frac{10\pi}{3} \end{eqnarray*}
$A-(B\cap C)+E-D-F=36\pi-\frac{10}{3}\pi+\frac{4}{3}\pi-\frac{4}{3}\pi-\frac{4}{3}\pi=\frac{94}{3}\pi$
$m+n=\boxed{97}$
[/hide]
whats up with the latex(?)

[hide="without calculus"]
The sum of regions X and Y is all points in sphere $A$ other than those in $D$, $F$, or the intersection of $B$ and $C$ not including $E$
Since $E$ is congruent to $D$, we can say that the volume of Y will not change if we take the points in $E$ and put them in $D$
This means that all points inside $A$ should be counted unless they are in either $F$ or the intersection of $B$ and $C$
Call the intersection of $B$ and $C$ region $Z$
The volume of the sums of X and Y is equivalent to ($A$-($Z$+$F$))
The volume of $A$ is $\frac{4\times3^{3}\times\pi}{3}$=$36\pi$
The volume of $F$ is $\frac{4\times1^{3}\times\pi}{3}$=$\frac{4\pi}{3}$
The volume of $Z$ is more complicated
$Z$ can be thought of as 2 congruent spherical caps
If this entire figure had been cut off by a plane down the center revealing all 6 spheres,
the intersection of $B$ and $C$ would resemble 2 gothic arches sharing a common base
(a gothic arch is 2 $60^\circ$ arcs of two congruent circles that pass through each other's centers)
This gothic arch would then have base 2, so it half its base is one, and its height is $\sqrt{3}$
The formula for volume of a spherical cap is $\frac{\pi}{6}\times(3r^{2}+h^{2})\times(h)$
radius = $\sqrt{3}$, height = 1
so the volume of 1 cap is $\frac{5\pi}{3}$
multiply by 2 to get the full intersection, which is  [b]$\frac{10\pi}{3}$[/b]
so $36\pi-(\frac{10\pi}{3}+\frac{4\pi}{3})=\frac{94\pi}{3}$
Answer is therefore $94+3=\textbf{97}$

I guess since I got the same answer as you then I was probably right. :) [/hide]

[quote="sapphyre571"]The formula for volume of a spherical cap is $\frac{\pi}{6}\times(3r^{2}+h^{2})\times(h)$[/quote]oh i didn't know that.. but thanks for telling me
[url=http://mathworld.wolfram.com/SphericalCap.html]mathworld spherical cap[/url]


How can we write $ AB$ as a vector in Latex, please.

\overrightarrow{AB} $ \overrightarrow{AB}$.  For just one letter use \vec $ \vec{a}$


calculus
integration
number theory
Diophantine equation

Let n^4 represent the 4th power of n.  Determine all non-negative integral solutions of (n1, n2, n3, ... , n14), if any, of the Diophantine equation

(n1)^4 + (n2)^4 + ... + (n14)^4 = 1,599.

[hide="BELLATRIX KILLS SIRIUS"]
Anything to the fourth power is either 0 or 1 mod 16, while 1599 is 15 mod 16. You can tell that this doesn't work out.
[/hide]


What is the largest possible size of an angle of a triangle formed
by joining the midpoints of three edges of a cube?

the midpoints of the edges of a cube can also be the vertices of a (regular) cuboctahedron (search on mathworld or something)

which can be oriented so that it stands on a triangular face and has a hexagonal equator

so the answer is at least 120 degrees, found by selecting 3 adjacent vertices on such a hexagonal equator (dont know how to explain that it is 120 and no more though)


Johns Hopkins Math Tournament(JHMT) will be held on 11/10 this year.

JHMT is a math tournament organized by Math Club in Johns Hopkins University.
It is held every year and around 100 students in Maryland come to the campus to compete.

There are two individual rounds: Algebra and Geometry/Combinatorics(you can choose between Geometry and Combinatorics).

There are two team rounds. One of the rounds is a logic puzzle round which will test you on creative problem solving skills rather than technical math skills. The other round will involve exploring a real world problem(e.g. physical science, mathematical finance, etc)

The registration for this event can be done online through teachers/coaches at [url]http://www.tripleintegral.org/jhmt[/url].
The deadline for the regitration is 10/13 and the late registration deadline is 10/21.
If you are a student and want to participate, let your teacher/coach know!

Are you sure you want to do this on the same day as PuMaC? :huh:

My coach sent them a letter asking them to move the date if possible, but apparently they can't or don't want to.  :(


probability
ratio
geometry
geometric transformation
rotation
counting
distinguishability

You have $ 4$ red marbles and $ 8$ blue marbles. Randomly, you put the $ 12$ marbles into a circle.  Find the probabilty that no two red marbles are next to each other.

Probability is the ratio successful over possible. Unfortunately, I can only provide a solution to the number possible. If someone would be so kind as to provide the other half of the solution, that would be very helpful.

The total number of ways to put the marbles is $ \frac{12!}{12}$. Remember that since we're working with a circle here, we divide by $ 12$ since there are twelve rotations of the same setup. $ \frac{12!}{12}\equal{}11!\equal{}39916800$.

[hide="hint 1"]
Since the marbles are in a ring and we don't want to have any red marbles next to eachother, we can simplify the question by first placing one blue marbel on the circle then considering the other $ 11$ marbles in a line.

[/hide]

[hide="hint 2"]
Now use the balls and urns method

[/hide]

[hide="answer"]

I got $ \frac {7}{33}$...
[/hide]

The answer is $ \frac{7}{33}$.
I just did it using complementary counting
-and the balls and urns method?

Balls and Urns - the "urns" are the spaces between two red marbles, and the balls are the blue marbles.  I'm not entirely sure why this analogy is used; I like to think of it as a divider argument.

First place one red marble on the circle.  Then we do the divider argument on 8 blue marbles and 3 red in a line.  We cannot have red marbles next to each other.  Thus each red acts as a divider- that is, we can only place reds between blues.  In a line of $ 8$ blues, we have $ 7$ places we can place the $ 3$ reds, thus \binom{7}{3} ways.  Since we are going in a circle... divide by 4 for the 4 groups of blues?  but this doesn't work if we have groups of say, 2,2,2,2, since there is only 1 way for this to happen, and other such examples.

I can't figure out how to account for the symmetry.

[hide]
Let a blue marble be always on top (to avoid rotations). Now let's place all the other blue marbles in a circle. No red can be next to another so we need to place reds between blues and we can do this in $ \binom 8 4$ ways (there are $ 8$ spaces, and we need to choose $ 4$ of them). Total number of ways without regard to position of reds would be $ \frac {11!}{7!\cdot 4!}$ so the probability is $ \frac {\binom 8 4}{\frac {11!}{7!\cdot 4!}} \equal{} \boxed{\frac {7}{33}}$[/hide]

I don't quite see where you get $ 11!/(7!4!)$ from...

I'm thinking the total number of possibilities could be found by breaking the $ 8$ blue marbles into groups of $ 0$ or more, with the reds serving to divide the groups.   "Add" in $ 4$ extra blue marbles so that we can then break them into groups of $ 1$ or more, and remove $ 1$ marble from each group at the end.  There are then $ \binom{12}{4} \equal{} 12!/(8!4!)$ places to place our red marbles.

I don't see a reason to be doing $ \binom{11}{4}$ here...  I guess if we took out 1 blue marble, and did the rest as a line (same result as distinguishable permuations); but I don't see exactly how this take out 1 marble idea forms a 1 to 1 correspondence with the circular arrangements...

He accounted for rotations by fixing a blue marble.
So, only $ 7$ blue marbles remain, and $ 4$ red marbles.
Since they are indistinguishable, there are $ \frac{11!}{7!4!}$ ways
to arrange them, since in each possibility you are overcounting
$ 4!7!$ times too many.

I get that it is indistinguishable permutations of 7 blue marbles and 4 red marbles.  It just seems to me that fixing one blue marble sort of distinguishes that marble, i.e. as if we have 7 identical blues and one that is different, which we fix.

But... it isn't counted as different from the others.  maybe....

Still, I don't quite see why this works.  Couldn't we just choose to fix a red marble?  Then we would have indistinguishable permutations of 8 blues and 3 reds, for $ 11!/(8!3!)$ possibilities, which would be different.  What would be wrong with this?

Yes, we could choose to fix a red marble.
The whole "fixing" can occur rigorously because it just accounts for rotations.  It may seem that it distinguishes a marble, but it doesn't.  This is because all of the marbles, based on the way Flame set up the problem, are considered indistinguishable.

Flame can do this, of course, because in doing probability the way in which you do it, as long as you do it in both the numerator and denominator, will give you the correct answer.

Therefore, you could just as easily assume the marbles are distinguishable, and as long as you consider that in both the numerator and denominator, you will again get the answer of $ \frac{7}{33}$.

And your way would have worked fine.  The thing about probability is that your numerators and denominators aren't necessarily the same, but their ratio is.  So, you can certainly fix a red marble, as long as you stick with that in your numerator.

I hope that cleared everything up a bit.

Yeah I think that does explain it quite a bit better.  I guess I was too fixed on the idea that probability is ways for event to occur over total outcomes.

First, I was trying to do distinguishable arrangements for the top, thinking that we only wanted to count those that were rotationally symmetrical to one another as 1, but I didn't fixate on that much - and I've realized, at least in terms of this probability, that it doesn't matter, because if there are symmetrical ways to arrange the marbles, then those arrangements are clearly more likely to occur.  We can ignore that.

I think the major thing I was missing is that we can consider one of blue marbles, in the ring of 8 before we place in the reds, as fixed.  I never really noted that before.  So when I suggested fixing a red, I was not thinking of doing that in the numerator too; I was thinking the numerator would not change.

Anyway, thanks for the help.  The only thing I can say is I have a [size=59]small[/size] doubt that the set up makes the marbles truly indistinguishable.  And, at this rate, it seems like this doubt will go away by tomorrow.