Difference between revisions of "2021 USAJMO Problems/Problem 1"

Revision as of 18:26, 15 April 2021

Problem

Let $\mathbb{N}$ denote the set of positive integers. Find all functions $f : \mathbb{N} \rightarrow \mathbb{N}$ such that for positive integers $a$ and $b,$ $f(a^2 + b^2) = f(a)f(b) \text{ and } f(a^2) = f(a)^2.$

Solution

I claim that the only function $f$ that satisfies the constraints outlined within the problem is the function $f(n) = 1$ for all positive integers $n$ .

We will proceed with strong induction. The base case is simple, as plugging $a=1$ into the second equation given within the problem gives $f(1)=f(1)^2$ . Since $f(n)$ can only return a positive integer value, we have that $f(1)=1$ .

Now we proceed with the inductive step. If the next number $n$ is either a perfect square or can be represented as a sum of two perfect squares, then obviously $f(n)=1$ , as it is either the product of two $f$ -values that are both equal to $1$ from the inductive assumption or is the square of an $f$ -value that is equal to $1$ , again due to the inductive assumption. Otherwise, we can use the Sum of Two Squares Theorem, which tells us that $n$ has at least one prime in its prime factorization that is $3(mod 4)$ and is raised to an odd power.

Lemma 1: Given that $a^2+b^2=c^2$ and $f(b)=f(c)=1$ , we then have $f(a)=1$ .

Proof: Note that the first condition in the problem tells us that $f(a^2+b^2)=f(a)f(b)$ , or $f(c^2)=f(a)f(b)$ . Using the second condition gives us $f(c)^2=f(a)f(b)$ . Plugging in the values of $f(b)$ and $f(c)$ gives us that $f(a)=1$ .

Now we will attempt to repeatedly remove prime factors that are $3(mod 4)$ and taken to an odd power, and we will move from the largest prime down to the smallest prime that satisfies above conditions. The prime factors will be removed by constructing a Pythagorean Triple with the prime being the smallest leg in the form of $p,\frac{p^2-1}{2},\frac{p^2+1}{2}$ (this will always work as $p\neq 2$ (not 3 mod 4), and this method works via Lemma 1). We will then prove the ending numbers that we achieve via removing all the $(\text{mod } 4)$ primes(which I will refer to as "tips") are equal to 1 b/c they can be expressed as the sum of two squares or is a perfect square(Sum of Two Squares Theorem). For example, if we took the number $21$ , we would first aim to remove the $7$ by splitting it into $24$ and $25$ , so $21$ would become $72$ and $75$ . $75$ is divisible by $3$ to an odd power, so we transform it into $100$ and $125$ . These two don't have any divisors that are $3 (\text{mod } 4)$ raised to an odd power so we leave it alone, as sum of two squares will work on them or they are perfect squares. $72$ does have a prime factor that is $3(\text{mod } 4)$ , but it is an even power so we leave it alone. In this case, the tips are $72$ , $100$ , and $125$ . However, now we need to prove two key facts: using this Pythagorean Triple Method will never generate another $3(\text{mod } 4)$ prime that is bigger than the current one we are working on or create more primes or keep the same number of primes in the tips' prime factorizations., as otherwise it could cause an infinite cycle, and also we must prove when we use Sum of Two Squares/Perfect Square given in the second condition on the tips the square root of the square(s) used will never be greater than or equal to $n$ .

The first claim can be proved rather simply. Note that $\frac{p^2-1}{2}$ can have no prime factors greater than or equal to $p$ , as it can be factored as $(p-1)(\frac{p+1}{2})$ , which are both less than $p$ and are integers( $p+1$ must be an integer due to $p$ must being odd(not equal to $2$ )). For $\frac{p^2+1}{2}$ , we can prove something a bit more general.

Lemma 2: For any positive integer $n$ , all prime factors of $n^2+1$ must be $1(\text{mod } 4)$ .

Proof: Note that if $n^2+1\equiv 0(\text{mod } p)$ , then we also must have $(n^2+1)(n^2-1)=(n^4-1)\equiv 0(\text{mod } p)$ , or $n^4 \equiv 1(\text{mod } p)$ . Now we can apply Fermat's Little Theorem to obtain $n^{p-1}\equiv 1(\text{mod } p)$ . Note that since $n$ and $n^2$ are obviously not $1(\text{mod } p)$ , as $n^2\equiv -1 (\text{mod } p)$ , we have that $p-1$ is a multiple of $4$ , or $p \equiv 1(\text{mod } 4)$ .

We can simply apply Lemma 2 to $p^2+1$ as $2$ is obviously not $3(\text{mod } 4)$ , and this means that a prime factor $3(\text{mod } 4)$ will never be generated from this term. This completes the first of our two claims.

Now we proceed to the second of our two claims. Note that every time we use the method on $n$ based on prime $p$ , we will multiply by around $\frac{p}{2}$ , clearly less than $p$ (if we multiply by $p$ we would get $p^2$ which is clearly greater than $\frac{p^2+1}{2}$ ). We will never have to use the same prime twice in our method, so at max in the end we will multiply $n$ by the product of a little less than all $3(mod 4)$ primes that divide it, which is less than $n$ itself for $n$ greater than or equal to $3$ (the smallest 3 mod 4 prime), meaning that the largest number that we must use two squares on that is generated by out method is less than $n^2$ . We need to prove that the two squares that sum to this are both less than $n$ , which is quite trivial, as they are less than $\sqrt{n^2}$ , which obviously means it must be less than $n$ . This proves the second of our claims.

This completes the second case of the inductive step, and therefore completes both the induction and the problem. ~Solution by hyxue

@@ Line 3: / Line 3: @@
 ==Solution==
+I claim that the only function <math>f</math> that satisfies the constraints outlined within the problem is the function <math>f(n) = 1</math> for all positive integers <math>n</math>.
+We will proceed with strong induction. The base case is simple, as plugging <math>a=1</math> into the second equation given within the problem gives <math>f(1)=f(1)^2</math>. Since <math>f(n)</math> can only return a positive integer value, we have that <math>f(1)=1</math>.
+Now we proceed with the inductive step. If the next number <math>n</math> is either a perfect square or can be represented as a sum of two perfect squares, then obviously <math>f(n)=1</math>, as it is either the product of two <math>f</math>-values that are both equal to <math>1</math> from the inductive assumption or is the square of an <math>f</math>-value that is equal to <math>1</math>, again due to the inductive assumption. Otherwise, we can use the Sum of Two Squares Theorem, which tells us that <math>n</math> has at least one prime in its prime factorization that is <math>3(mod 4)</math> and is raised to an odd power.
+Lemma 1: Given that <math>a^2+b^2=c^2</math> and <math>f(b)=f(c)=1</math>, we then have <math>f(a)=1</math>.
+Proof: Note that the first condition in the problem tells us that <math>f(a^2+b^2)=f(a)f(b)</math>, or <math>f(c^2)=f(a)f(b)</math>. Using the second condition gives us <math>f(c)^2=f(a)f(b)</math>. Plugging in the values of <math>f(b)</math> and <math>f(c)</math> gives us that <math>f(a)=1</math>.
+Now we will attempt to repeatedly remove prime factors that are <math>3(mod 4)</math> and taken to an odd power, and we will move from the largest prime down to the smallest prime that satisfies above conditions. The prime factors will be removed by constructing a Pythagorean Triple with the prime being the smallest leg in the form of <math>p,\frac{p^2-1}{2},\frac{p^2+1}{2}</math>(this will always work as <math>p\neq 2</math>(not 3 mod 4), and this method works via Lemma 1). We will then prove the ending numbers that we achieve via removing all the <math>(\text{mod } 4)</math> primes(which I will refer to as "tips") are equal to 1 b/c they can be expressed as the sum of two squares or is a perfect square(Sum of Two Squares Theorem). For example, if we took the number <math>21</math>, we would first aim to remove the <math>7</math> by splitting it into <math>24</math> and <math>25</math>, so <math>21</math> would become <math>72</math> and <math>75</math>. <math>75</math> is divisible by <math>3</math> to an odd power, so we transform it into <math>100</math> and <math>125</math>. These two don't have any divisors that are <math>3 (\text{mod } 4)</math> raised to an odd power so we leave it alone, as sum of two squares will work on them or they are perfect squares. <math>72</math> does have a prime factor that is <math>3(\text{mod } 4)</math>, but it is an even power so we leave it alone. In this case, the tips are <math>72</math>, <math>100</math>, and <math>125</math>. However, now we need to prove two key facts: using this Pythagorean Triple Method will never generate another <math>3(\text{mod } 4)</math> prime that is bigger than the current one we are working on or create more primes or keep the same number of primes in the tips' prime factorizations., as otherwise it could cause an infinite cycle, and also we must prove when we use Sum of Two Squares/Perfect Square given in the second condition on the tips the square root of the square(s) used will never be greater than or equal to <math>n</math>.
+The first claim can be proved rather simply. Note that <math>\frac{p^2-1}{2}</math> can have no prime factors greater than or equal to <math>p</math>, as it can be factored as <math>(p-1)(\frac{p+1}{2})</math>, which are both less than <math>p</math> and are integers(<math>p+1</math> must be an integer due to <math>p</math> must being odd(not equal to <math>2</math>)). For <math>\frac{p^2+1}{2}</math>, we can prove something a bit more general.
+Lemma 2: For any positive integer <math>n</math>, all prime factors of <math>n^2+1</math> must be <math>1(\text{mod } 4)</math>.
+Proof: Note that if <math>n^2+1\equiv 0(\text{mod } p)</math>, then we also must have <math>(n^2+1)(n^2-1)=(n^4-1)\equiv 0(\text{mod } p)</math>, or <math>n^4 \equiv 1(\text{mod } p)</math>. Now we can apply Fermat's Little Theorem to obtain <math>n^{p-1}\equiv 1(\text{mod } p)</math>. Note that since <math>n</math> and <math>n^2</math> are obviously not <math>1(\text{mod } p)</math>, as <math>n^2\equiv -1 (\text{mod } p)</math>, we have that <math>p-1</math> is a multiple of <math>4</math>, or <math>p \equiv 1(\text{mod } 4)</math>.
+We can simply apply Lemma 2 to <math>p^2+1</math> as <math>2</math> is obviously not <math>3(\text{mod } 4)</math>, and this means that a prime factor <math>3(\text{mod } 4)</math> will never be generated from this term. This completes the first of our two claims.
+Now we proceed to the second of our two claims. Note that every time we use the method on <math>n</math> based on prime <math>p</math>, we will multiply by around <math>\frac{p}{2}</math>, clearly less than <math>p</math>(if we multiply by <math>p</math> we would get <math>p^2</math> which is clearly greater than <math>\frac{p^2+1}{2}</math>). We will never have to use the same prime twice in our method, so at max in the end we will multiply <math>n</math> by the product of a little less than all <math>3(mod 4)</math> primes that divide it, which is less than <math>n</math> itself for <math>n</math> greater than or equal to <math>3</math>(the smallest 3 mod 4 prime), meaning that the largest number that we must use two squares on that is generated by out method is less than <math>n^2</math>. We need to prove that the two squares that sum to this are both less than <math>n</math>, which is quite trivial, as they are less than <math>\sqrt{n^2}</math>, which obviously means it must be less than <math>n</math>. This proves the second of our claims.
+This completes the second case of the inductive step, and therefore completes both the induction and the problem.
+~Solution by hyxue
 == See Also ==

2021 USAJMO (Problems • Resources)
Preceded by First Question	Followed by Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

Page

Toolbox

Search

Difference between revisions of "2021 USAJMO Problems/Problem 1"

Revision as of 18:26, 15 April 2021

Problem

Solution

See Also