Problem:
Let $P(x)=x^3-x+1$. Prove that, for every natural number $n > 1$, the numbers $n,P(n),P(P(n)),\ldots$ taken pairwise are relatively primes.
Solution:
Let $P_k(n)=\underbrace{P(P(\ldots P(n))))}_{k \ \textrm{times}}$. We prove by induction on $k \in \mathbb{N}^*$ that $P_k(n) \equiv 1 \pmod{P_i(n)}$ for every $0 \leq i \leq k-1$, where we set $P_0(n)=n$. In this way it's clear that taken two arbitrary numbers from the sequence, they will be relatively primes. If $k=1$ it is trivial, since $P(n)-n(n^2-1)=1$. Suppose that the statement is true for some $k$. Then, $$P_{k+1}(n)=P^3_{k}(n)-P_{k}(n)+1 \equiv 1 \pmod{P_{k}(n)}$$ and by induction hypothesis, $P_k(n) \equiv 1 \pmod{P_i(n)}$ for every $0 \leq i \leq k-1$, so $P_{k+1}(n) \equiv 1 \pmod{P_i(n)}$ for every $0 \leq i \leq k$ and the desired conclusion follows by the Principle of Mathematical Induction.
Showing posts with label Italian TST. Show all posts
Showing posts with label Italian TST. Show all posts
Friday, December 2, 2011
Thursday, December 1, 2011
Italian IMO Team Selection Test 1988
Problem:
Decompose the natural number $n$ into a sum of natural numbers so that the product of the summands is maximum.
Solution:
We go further and give explicitly the maximum product. Let $n=a_1+a_2+\ldots+a_m$ and $P=a_1a_2\cdots a_m$, where $a_i \in \mathbb{N}^*$ for every $1 \leq i \leq m$ . If $n=1,2$, clearly $P_{\max}=1$. Assume $n > 2$. To maximize $P$, any number $a_i$ can't be $1$ since $a_i + 1 > a_i \cdot 1$ for every $1 \leq i \leq m$ and we can replace the two summands $a_i$ and $1$ with $a_i + 1$. Likewise, if $a_i > 4$, we can replace $a_i$ with $(a_i-2)+2$ since $2(a_i-2) > a_i$. At last, we observe that it's indifferent to have $4$ or $2+2$, so $P$ can be maximized with $2$'s and $3$'s. Since $3^2 > 2^3$, we can have at most two summands equal to $2$ since we can replace $2+2+2$ with $3+3$. To be more precise, we have $$P_{max} = \left\{ \begin{array}{lll} 3^k & \textrm{if } n=3k \\ 2^2 \cdot 3^{k-1} & \textrm{if } n=3k+1 \\ 2\cdot 3^k & \textrm{if } n=3k+2 \end{array} \right.$$ where $k \in \mathbb{N}^*$.
Decompose the natural number $n$ into a sum of natural numbers so that the product of the summands is maximum.
Solution:
We go further and give explicitly the maximum product. Let $n=a_1+a_2+\ldots+a_m$ and $P=a_1a_2\cdots a_m$, where $a_i \in \mathbb{N}^*$ for every $1 \leq i \leq m$ . If $n=1,2$, clearly $P_{\max}=1$. Assume $n > 2$. To maximize $P$, any number $a_i$ can't be $1$ since $a_i + 1 > a_i \cdot 1$ for every $1 \leq i \leq m$ and we can replace the two summands $a_i$ and $1$ with $a_i + 1$. Likewise, if $a_i > 4$, we can replace $a_i$ with $(a_i-2)+2$ since $2(a_i-2) > a_i$. At last, we observe that it's indifferent to have $4$ or $2+2$, so $P$ can be maximized with $2$'s and $3$'s. Since $3^2 > 2^3$, we can have at most two summands equal to $2$ since we can replace $2+2+2$ with $3+3$. To be more precise, we have $$P_{max} = \left\{ \begin{array}{lll} 3^k & \textrm{if } n=3k \\ 2^2 \cdot 3^{k-1} & \textrm{if } n=3k+1 \\ 2\cdot 3^k & \textrm{if } n=3k+2 \end{array} \right.$$ where $k \in \mathbb{N}^*$.
Wednesday, November 30, 2011
Italian IMO Team Selection Test 1994 - Problem 2
Problem:
Find all prime numbers $p$ for which $\dfrac{2^{p-1}-1}{p}$ is a perfect square.
Solution:
Since $2^{p-1}-1$ is odd for all primes $p$, it's easy to see that $p \neq 2$. Moreover, by Fermat's Little Theorem we have $2^{p-1} \equiv 1 \pmod{p}$ for all primes $p \neq 2$, so $\dfrac{2^{p-1}-1}{p}$ is an integer and we want this integer to be a perfect square. Then, $$pn^2 = 2^{p-1} - 1, \quad n \in \mathbb{N}.$$ Since $p > 2$, $p-1$ is even and so we can write $$pn^2=(2^{\frac{p-1}{2}}-1)(2^{\frac{p-1}{2}}+1).$$ Both factor on the right hand side are odd and are relatively primes since their difference is $2$. This means that $p$ divides exactly one between the two factors and the other is a perfect square. If $p$ divides the first factor, we have $$2^{\frac{p-1}{2}}-1=pa^2, \qquad 2^{\frac{p-1}{2}}+1=b^2$$ where $a,b \in \mathbb{N}^*$. From the second equation we find $2^{\frac{p-1}{2}}=(b-1)(b+1)$ and these two factors are both powers of $2$ whose difference is $2$, so $b=3$ and $p=7$. If $p$ divides the second factor, we have $$2^{\frac{p-1}{2}}-1=a^2, \qquad 2^{\frac{p-1}{2}}+1=pb^2$$ and from the first equation, if $p>3$ then $2^{\frac{p-1}{2}}-1=a^2 \equiv 3 \pmod{4}$, contradiction. So, it must be $p=3$ and for such value, $\dfrac{2^{3-1}-1}{3}=1$ which is a perfect square. In conclusion, the only prime numbers $p$ which satisfy the given condition are $p=3$ and $p=7$.
Find all prime numbers $p$ for which $\dfrac{2^{p-1}-1}{p}$ is a perfect square.
Solution:
Since $2^{p-1}-1$ is odd for all primes $p$, it's easy to see that $p \neq 2$. Moreover, by Fermat's Little Theorem we have $2^{p-1} \equiv 1 \pmod{p}$ for all primes $p \neq 2$, so $\dfrac{2^{p-1}-1}{p}$ is an integer and we want this integer to be a perfect square. Then, $$pn^2 = 2^{p-1} - 1, \quad n \in \mathbb{N}.$$ Since $p > 2$, $p-1$ is even and so we can write $$pn^2=(2^{\frac{p-1}{2}}-1)(2^{\frac{p-1}{2}}+1).$$ Both factor on the right hand side are odd and are relatively primes since their difference is $2$. This means that $p$ divides exactly one between the two factors and the other is a perfect square. If $p$ divides the first factor, we have $$2^{\frac{p-1}{2}}-1=pa^2, \qquad 2^{\frac{p-1}{2}}+1=b^2$$ where $a,b \in \mathbb{N}^*$. From the second equation we find $2^{\frac{p-1}{2}}=(b-1)(b+1)$ and these two factors are both powers of $2$ whose difference is $2$, so $b=3$ and $p=7$. If $p$ divides the second factor, we have $$2^{\frac{p-1}{2}}-1=a^2, \qquad 2^{\frac{p-1}{2}}+1=pb^2$$ and from the first equation, if $p>3$ then $2^{\frac{p-1}{2}}-1=a^2 \equiv 3 \pmod{4}$, contradiction. So, it must be $p=3$ and for such value, $\dfrac{2^{3-1}-1}{3}=1$ which is a perfect square. In conclusion, the only prime numbers $p$ which satisfy the given condition are $p=3$ and $p=7$.
Subscribe to:
Posts (Atom)