Call a set of 3 positive integers $\{a,b,c\}$ a Pythagorean set if $a,b,c$ are the lengths of the 3 sides of a right-angled triangle. Prove that for any 2 Pythagorean sets $P,Q$, there exists a positive integer $m\ge 2$ and Pythagorean sets $P_1,P_2,\ldots ,P_m$ such that $P=P_1, Q=P_m$, and $\forall 1\le i\le m-1$, $P_i\cap P_{i+1}\neq \emptyset$.
Problem
Source: China Mathematical Olympiad 2019 Q2
Tags: number theory, Hi
14.11.2018 23:17
It's easy
14.11.2018 23:34
15.11.2018 14:27
Let $\to$ denote if I can go from one triplet to another via a finite sequence of triplets. Note that we only need to show that any $(p,q,r)\to (3,4,5)$. First we show that $(3,4,5)\to (3k,4k,5k)$ for any positive integer $k$. We denote the set $\mathbb{S}$ as the current set of $k$ that works. Lemma 1: For any prime $p$, if $p\in \mathbb{S}$, then $(3k,4k,5k)\to (3kp,4kp,5kp)$ for all $k$. This is easy to show. Lemma 2: If primes $p_1,p_2,...,p_n \in \mathbb{S}$, then any $k$ whose prime factorization consists of only those primes is also in $\mathbb{S}$. This follows from Lemma 1. First we show that $p=2\in \mathbb{S}$. Note that $(3,4,5)\to (5,12,13)\to (9,12,15)\to (15,20,25)\to (7,24,25)\to (10,24,26) \to (6,8,10)$. Now proceed with induction. Suppose the $n$ smallest primes $p_1,p_2,...,p_n\in \mathbb{S}$, then for the next smallest prime $q$, $(3q,4q,5q)\to (4q,2q^2-2,2q^2+2)$. Note that $2q^2-2=2(q-1)(q+1)$ can only consists of factors among $p_1,p_2,...,p_n$. Furthermore, $q$ is odd so $4|2q^2-2$, and thus $\frac{2q^2-2}{4}\in \mathbb{S}$ from Lemma 2. Hence $(3,4,5)\to (3\cdot\frac{2q^2-2}{4},2q^2-2,5\cdot\frac{2q^2-2}{4})\to (4q,2q^2-2,2q^2+2)\to (3q,4q,5q)$ implying that $q\in \mathbb{S}$, finishing the induction. As all primes are in $\mathbb{S}$, from Lemma 2 all positive integers must also be in $\mathbb{S}$. Finishing, for any triplet $(p,q,r)$, at least one of $p,q,r$ is divisible by $3$, and so $(p,q,r)\to (3,4,5)$.
19.01.2019 03:51
61plus wrote: $$(3\cdot\frac{2q^2-2}{4},2q^2-2,5\cdot\frac{2q^2-2}{4})\to (4q,2q^2-2,2q^2+2)$$ Why is this true? Also, the above proof seems to only show that $(3k, 4k, 5k)$ can be reached from $(3, 4, 5)$. I thought you're supposed to show that $(p, q, r)$ can be achieved from $(3, 4, 5)$ for any pythagorean triplet $(p, q, r)$? Or am I missing something?
19.01.2019 17:12
EDIT: nvm I forgot that $(a, b, c) \rightarrow (a, d, e)$ for any two triplets $(a, b, c)$ and $(a, d, e)$; thus, my question was trivial.
19.01.2019 19:15
arvind_r wrote: 61plus wrote: $$(3\cdot\frac{2q^2-2}{4},2q^2-2,5\cdot\frac{2q^2-2}{4})\to (4q,2q^2-2,2q^2+2)$$ Why is this true You can verify that the two pairs are both Pythagorean triplets.
19.01.2019 19:17
arvind_r wrote: Also, the above proof seems to only show that $(3k, 4k, 5k)$ can be reached from $(3, 4, 5)$. I thought you're supposed to show that $(p, q, r)$ can be achieved from $(3, 4, 5)$ for any pythagorean triplet $(p, q, r)$? Or am I missing something? This part is proved in the last line, which I will elaborate a little. Since one of $(p,q,r)$ is divisible by $3$, WLOG let it be $p=3k$. Then $(3k,q,r)\rightarrow(3k,4k,5k)\rightarrow(3,4,5)$
29.09.2019 10:35
Let $G$ be an infinite graph with vertex set $V=\{3,4,5,6,7,8,\ldots\}$, and an edge between $a$ and $b$ if and only if there is some other positive integer $c$ such that $\{a,b,c\}$ is a Pythagorean triple. Label the edge by that Pythagorean triple. We'll show that for any two vertices in $G$, there is a finite path connecting them. This solves the problem as the sequence of edges in the path becomes are sequence of interpolating Pythagorean triples. Note that if there is a path from $a$ to $b$, then there is also a path from $ka$ to $kb$ since we can multiply all the Pythagorean triples that interpolate from $a$ to $b$ by $k$. This is the fact that will allow us to solve the problem. We claim that there is a finite path from $n$ to $3$ for any $n\ge 3$. The proof proceeds by strong induction on $n$, with the base cases $n=3,4,5$ being obvious. We will actually need the base case $n=6$ as well, and the path to $3$ is as follows: \[6\to 8\to 15\to 12\to 5\to 3.\]Now suppose we have some vertex $n\ge 7$, and for all $3\le m<n$, we have that $m$ is connected to $3$. Suppose $n$ has a factor between $4$ and $n-1$ inclusive, call it $m$. Then, we see that $n=mk$, and since $m$ has a path to $3$, we have that $n$ has a path to $3k$. Since $m\ge 4$, we have that $3k<n$, so by the inductive hypothesis there is a path from $3k$ to $3$, so there is a path from $n$ to $3$. Now, suppose that all factors of $n$ are in $\{1,2,3,n\}$. It's not hard to see that since $n\ge 7$, we can't have $n$ even, so $n=2k+1$ for some $k\ge 3$ (this is why we had to deal with $n=6$ separately). We have the Pythagorean triple $\{2k+1,2k(k+1),2k(k+1)+1\}$, so there is an edge connecting $2k+1\to 2k(k+1)$. However, $k,k+1<2k+1$, so there is a path from $k$ to $3$ and $k+1$ to $3$, so there is a path from $2k(k+1)$ to $2\cdot 3\cdot 3=18$. There's a path from $6$ to $3$ and $3$ to $5$, so there is a path from $6$ to $5$, so there is a path from $18=6\cdot 3$ to $5\cdot 3=15$. We have the triple $\{8,15,17\}$, so there is a path from $18$ to $8$, and clearly $8$ is connected to $6$. Thus, from $2k+1$, we can reach $6$, which is connected to $3$, as desired. This completes the induction, and thus the proof.
26.04.2020 13:17
yayups wrote: there is a path from $k$ to $3$ and $k+1$ to $3$, so there is a path from $2k(k+1)$ to $2\cdot 3\cdot 3=18$ I don't think this is obvious. You first need to prove that if pairs of vertices $(a,b)$ and $(c,d)$ are adjacent in $G$ then there exists an edge between $ac$ and $bd$.
26.04.2020 13:54
Write $a\to b$ if there is a path from a Pythagorean triple containing $a$ to another triple containing $b$. It suffices to show that $3\to n$ for any positive integer $n\geq 3$, which we will do so by induction. Note that if $a\to b$, then $at\to bt$ for some factor $t$ since we can just scale all the triples in the path, and that $a\to b\iff b\to a$. Firstly, $3\to 6$ because $$(3,4,5),(5,12,13),(9,12,15),(8,15,17),(6,8,10) $$is a valid path. Also, $3\to 3,4,5$ holds trivially. Now suppose $3\to n$ for all $n\leq k$. We consider two cases based on the parity of $k+1$. If $k+1$ is even, then $3\to \frac{k+1}{2}$ by the induction, which implies $6\to k+1$, so $3\to 6\to k+1$ as required. If $k+1$ is odd, then by observing that $\left(k+1, \frac{k(k+2)}{2}, \frac{k(k+2)+2}{2}\right)$ is a Pythagorean triple, we have $k+1\to \frac{k(k+2)}{2}$. Then since $4\to 3\to k$ by the induction, \begin{align*} k&\to 4 \\ \implies \frac{k(k+2)}{2} &\to \frac{4(k+2)}{2} \\\implies \frac{k(k+2)}{2} &\to 2(k+2) \\ \implies k+1 &\to 2(k+2)\end{align*}It now suffices to show $3\to 2(k+2)$. Since $k$ is even and $\frac{k+2}{2}\leq k$, $3\to \frac{k+2}{2}$ implies $12\to 2(k+2)$. But $(3,4,5),(5,12,13)$ is a valid path which shows $3\to 12$, and hence $3\to 2(k+2)$. This means that $3\to k+1$, so that in all cases, the induction is complete.
26.04.2020 14:10
#11 looks fine, good job
06.05.2020 11:20
We call two natural number $a$ and $b$ connected and denote it by $a\sim b$ if there exists positive integer $m\ge 2$ and Pythagorean sets $P_1,P_2,\ldots ,P_m$ such that $a\in P_1, b\in P_m$, and $\forall 1\le i\le m-1$, $P_i\cap P_{i+1}\neq \emptyset$. $\underline{Lemma 1.}$Every Pythgorean set consists of at least one multiple of 5 $\underline{Proof.}$Pythgorean sets are of the form $$\{d(m^2+n^2),2dmn,d(m^2-n^2\}$$therefore, if one of $m,n$ is divisible by $5$ then we are done. Otherwise since $m^2,n^2\equiv 1,4\mod 5$, one of $m^2+n^2$ and $m^2-n^2$ must be a multiple of $5$, so we are done. $\underline{Lemma 2.}$If $a\sim b$ then $ka\sim kb$ for all natural number $k$ $\underline{Proof.}$Since $a\sim b$, there exists integer $m\ge 2$ and Pythagorean sets $P_1,P_2,\ldots ,P_m$ such that $P=P_1, Q=P_m$, and $\forall 1\le i\le m-1$, $P_i\cap P_{i+1}\neq \emptyset$. Notice that if $P_i$ is a Pythgorean set then $kP_i$ is also a Pythgorean set. Therefore considering the sets $$kP_1,kP_2,...,kP_m$$then we have $ka\sim kb$. \newline Now we return to the original problem. $\underline{CLAIM}$For every integer $n$, $5n\sim 5$ $\underline{Proof.}$We proceed by induction on $n$. The base cases are trivial, and in particular $5\sim 10$. Hence $5n\sim 5$ then $10n\sim 10\sim 5$. Therefore $10n\sim 5$. Now suppose all smaller cases hold, consider the case $n$, if $n=2k$, then we have $5n=10k\sim 5$ so we are done. Otherwise let $n=2k+1$. Notice that $$\{5((k+1)^2+k^2),10k+5,10k(k+1)\}$$is a Pythgorean set. Therefore $10k+5\sim 10k(k+1)$. Since $10k\sim 5$ by inductive hypothesis, $10k(k+1)\sim 5(k+1)\sim 5$ Hence $$10k+5\sim 5$$Therefore every multiple of $5$ is connected to $5$, applying Lemma 1, we are done.
28.05.2020 10:28
mofumofu wrote: Call a set of 3 positive integers $\{a,b,c\}$ a Pythagorean set if $a,b,c$ are the lengths of the 3 sides of a right-angled triangle. Prove that for any 2 Pythagorean sets $P,Q$, there exists a positive integer $m\ge 2$ and Pythagorean sets $P_1,P_2,\ldots ,P_m$ such that $P=P_1, Q=P_m$, and $\forall 1\le i\le m-1$, $P_i\cap P_{i+1}\neq \emptyset$. Nice and easy problem . We define an operation on a Pythagorean $P$ to be something which takes it to another Pythagorean $P'$ such that $P\cap P'\neq\Phi$ For $k\in\mathbb{N}$ we say that property $P(k)$ is true if we can reach $(3k,4k,5k)$ starting from $(3,4,5)$ We say that the property $Q(n)$ is true if $P(k)\implies P(nk)$ Note : $Q(a)$ and $Q(b) \implies Q(ab)$ We prove by induction that $Q(p)$ is true for all primes $p$ Base step- $p=2$ $(3k,4k,5k)\rightarrow(5k,12k,13k)\rightarrow(9k,12k,15k)\rightarrow(8k,15k,17k)\rightarrow(3(2k),4(2k),5(2k))$ Assumption step- Assume $Q(p)$ holds for all primes $p<r$ where $r>2$ is a prime. Induction step- We prove $Q(r)$ As $r>2$ all prime divisors of $\frac{r^2-1}2$ are less than $r$ and hence by assumption and Note we have $Q(\frac{r^2-1}2)$ is true . Now $(3k,4k,5k)\rightarrow(3k(\frac{r^2-1}2),4k(\frac{r^2-1}2),5k(\frac{r^2-1}2))\rightarrow(3k(\frac{r^2-1}2),3kr,3k(\frac{r^2+1}2))\rightarrow(3kr,4kr,5kr)$ And hence $Q(r)$ is true. Hence $Q(n)$ is true for all $n\in\mathbb{N}$ This along with the fact that $P(1)$ is true implies that $P(k)$ is true for all $k\in\mathbb{N}$ Now let $\{a,b,c\}$ be a Pythagorean , it is well known that $3|abc$ WLOG $3|a$ so $a=3t$ , then $(3,4,5)\rightarrow(3t,4t,5t)\rightarrow\{a,b,c\}$ And hence any Pythagorean can be reached through $(3,4,5)$, now as the operation is reversible we can reach any Pythagorean from any other Pythagorean. Hence proved.
31.05.2020 11:10
Say $(a_1,b_1,c_1) \sim (a_2,b_2,c_2)$ if we can get from the first triple to the second via a sequence. It is not hard to show that any Pythagorean triple contains a multiple of 3. Therefore, it suffices to show $(3,4,5)\sim (3n,4n,5n)$ for any $n\ge 2$; then, in any triple, we use the multiple of 3 to get to something of the form $(3n,4n,5n)$, then go to $(3,4,5)$, then go to the multiple of 3 in the triple we want (the chain is reversible). Key Claim: $(3k,4k,5k)\sim (3kp,4kp,5kp)$ for any $k\ge 1$ and any prime $p$. Proof: We fix $k$ and strong induct on $p$. The base case is $p=2$: we need to show $(3k,4k,5k) \sim (6k,8k,10k)$. Note the sequence \[ (3,4,5) \to (5,12,13) \to (9,12,15) \to (8,15,17) \to (6,8,10). \]Multiplying everything above by $k$ shows the base case. Now, we prove it for $p$ assuming $(3k,4k,5k) \sim (3kq, 4kq, 5kq)$ for any $q<p$. The key is to notice the following chain: \begin{align*} (3k,4k,5k) &\sim \left(3k \left(\tfrac{p^2-1}{2}\right), \ 4k\left(\tfrac{p^2-1}{2}\right), \ 5k\left(\tfrac{p^2-1}{2}\right)\right) \\ &\to \left( 5kp, \ 5k\left(\tfrac{p^2-1}{2}\right), \ 5k\left(\tfrac{p^2+1}{2}\right) \right) \\ &\to (3kp,4kp,5kp). \end{align*}Note that the first $\sim$ follows since all prime divisors of $\tfrac{p^2-1}{2}=\tfrac12(p-1)(p+1)$ are less than $p$, and hence by induction we can multiply in the primes dividing $\tfrac{p^2-1}{2}$ into $(3k,4k,5k)$. This proves the claim. $\square$ Now we can start from $(3,4,5)$, and multiply in the primes we need, so that we end with $(3n,4n,5n)$. This completes the proof.
13.06.2020 06:45
Eyed has an amazing solution he told me to post: Eyed wrote: Denote $P$ and $Q$ as connected if such a finite sequence exists. "Connected" is a symmetric and transitive property. Also denote $P \rightarrow Q$ if $P\cap Q\neq \phi$. I will first prove the following claims: Claim 1: Any $P = (3,4,5)$, $Q = (2^{k}\cdot 3, 2^{k}\cdot 4, 2^{k}\cdot 5)$ is connected. Proof 1: First, I show that $(3,4,5)$ and $(6,8,10)$ are connected. This is because we have: \[(3,4,5) \rightarrow (5,12,13)\rightarrow(9,12,15)\rightarrow(8,15,17)\rightarrow(6,8,10)\] Then, it is easy to see that if $P = (3a, 4a, 5a), Q = (6a, 8a, 10b)$, then $P$ is connected to $Q$. Since connected is transitive, we can see that $(3,4,5)$ is connected to $(2^{k}\cdot3, 2^{k}\cdot4, 2^{k}\cdot 5)$. Claim 2: Any $P = (3,4,5)$ and $Q = (p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\ldots p_{n}^{\alpha_{n}}\cdot3, p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\ldots p_{n}^{\alpha_{n}}\cdot4, p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\ldots p_{n}^{\alpha_{n}}\cdot 5)$ is connected, where $p_{i}$ is a prime and $p_{i} < p_{j}$ for $i<j$. Proof. We will use induction on the largest prime in $p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\ldots p_{n}^{\alpha_{n}}$, notably $p_{n}$. The first prime, $p_{1} = 2$, satisfies from claim 1. We need to prove that $(3,4,5)$ is connected to $(3p_{n}, 4p_{n}, 5p_{n})$, because then that means $(3,4,5)$ is connected to $(3p_{n}^{\alpha_{n}}, 4p_{n}^{\alpha_{n}}, 5p_{n}^{\alpha_{n}})$, and by our inductive hypothesis, this means $(3,4,5)$ is connected to \[(3p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\ldots p_{n-1}^{\alpha_{n-1}}, 4p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\ldots p_{n-1}^{\alpha_{n-1}}, 5p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\ldots p_{n-1}^{\alpha_{n-1}})\]is connected to \[(p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\ldots p_{n}^{\alpha_{n}}\cdot3, p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\ldots p_{n}^{\alpha_{n}}\cdot4, p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\ldots p_{n}^{\alpha_{n}}\cdot 5)\]So, we prove that $(3,4,5)$ is connected to $(3p_{n}, 4p_{n}, 5p_{n})$. For the inductive step, observe that if $p_{n} = 2r+1$, then $(2r+1, 2r^{2} + 2r + 1, 2r^{2} + 2r)$ is a Pythagorean triple. Then, we get: \[(3p_{n}, 4p_{n}, 5p_{n}) \rightarrow (3\cdot (2r+1), 3\cdot (2r^{2} + 2r), 3\cdot (2r^{2} + 2r + 1))\] Since $4|2r^{2} + 2r$, and for any $q | 2r^{2} + 2r$ we have $q<p_{n}$, we have \[(3\cdot (2r+1), 3\cdot (2r^{2} + 2r), 3\cdot (2r^{2} + 2r + 1))\rightarrow (3x, 4x, 5x)\] Where the prime factors of $x$ are less than $p_{n}$, and $4x = 2r^{2} + 2r$. By our inductive hypothesis, this is connected to $(3,4,5)$, so our inductive step is proven. Therefore, all $(3a, 4a,5a)$ is connected to $(3b,4b,5b)$. Finally, I claim any pythagorean triple $(a,b,c)$ is connected to some $(3x,4x,5x)$. This is because one of $a,b,c$ must be a multiple of $4$, so we can find a $x$ such that $4x = $ $a$ or $b$ or $c$. Thus, all pythagorean triples must be connected, which is what we wanted to prove.
03.03.2022 06:21
It is sufficient to show that we can get from any Pythagorean triple to $(3,4,5)$. Indeed, notice that for any Pythagorean triple $a^2+b^2=c^2$, either $a$ or $b$ is divisible by $3$. Thus, we can get from $(a,b,c)$ to $(3n,4n,5n)$ for some positive integer $n$. Now, we claim that we can get from $(3n,4n,5n)$ to $(3,4,5)$ for any positive integer $n$. Indeed, we will induct on $n$. The basis $n=2$ goes as follows \[ (6,8,10) \to (8,15,17) \to (9,12,15) \to (5,12,13) \to (3,4,5) \]Now, for the inductive step. Assume it works for all $k<n$. We get two cases. Case 1: $k$ is composite. Let $k=ab$ for $k>a,b>1$. By our hypothesis \[ (3ab,4ab,5ab) \to (3a,4a,5a) \to (3,4,5) \] Case 2: $k$ is prime. We have $(3k,4k,5k) \to \left ( 3k, \dfrac{3(k^2-1)}{2}, \dfrac{3(k^2+1)}{2} \right )$. if $k^2-1=p_1p_2 \cdots p_m$ for primes $p_1,p_2,...,p_m$. Notice that $p_i<k$ for all $i \le m$. So by our hypothesis. \[(3p_1p_2 \cdots p_m,4p_1p_2 \cdots p_m,5p_1p_2 \cdots p_m) \to (3p_1p_2 \cdots p_{m-1},4p_1p_2 \cdots p_{m-1},5p_1p_2 \cdots p_{m-1}) \to \cdots \to (3,4,5)\] Completing induction. $\blacksquare$
17.06.2022 22:05
Write $A \to B$ if we can go from $A$ to $B$ via a chain of overlapping Pythagorean sets. Note that $A \to B \implies B \to A$, and that if $(a,b,c) \to (e,f,g)$, then $(ak,bk,ck) \to (ek,fk,gk)$. We will show that for any Pythagorean set $(a,b,c)$, we have $(a,b,c) \to (3,4,5)$, which solves the problem. If we have $(3,4,5) \to (3a,4a,5a)$ and $(3,4,5) \to (3b,4b,5b)$, we can go from $(3,4,5) \to (3a,4a,5a) \to (3ab,4ab,5ab)$. Hence it suffices to show that we have $(3,4,5) \to (3p,4p,5p)$ for all primes $p$. For $p=2$, note that we have $$(3,4,5) \to (5,12,13) \to (9,12,15) \to (15,20,25) \to (7,24,25) \to (10,24,26) \to (6,8,10).$$Further, by induction on this fact, we have $(3,4,5) \to (3\cdot 2^i,4\cdot 2^i,5\cdot 2^i)$. Labelling the primes $2=p_1<p_2<\cdots$, we will finish with induction on the claim that $(3,4,5) \to (3p_i,4p_i,5p_i)$ for $1 \leq i \leq n$, with the claim being true for $n=1$. Let $q=p_{n+1}$ for convenience. Then $(3q,4q,5q) \to (4q,2q^2-2,2q^2+2)$. Further, since $\tfrac{2q^2-2}{4}=(q-1)\cdot \tfrac{q+1}{2}$ is an integer, all of whose prime factors are less than $q$, so by inductive hypothesis we have $(3,4,5) \to S$ where $S$ is a Pythagorean set that contains $2q^2-2$. Since $S \to (4q,2q^2-2,2q^2+2) \to (3q,4q,5q)$, this completes the induction, so we're done. $\blacksquare$
25.10.2023 19:29
Observe that from $\pmod{8}$ we see that every pythagorean triple has a multiple of $4$. Therefore, it suffices to show to show that any two $3,4,5$ scale triples can reach each other. Claim: We can get from $3a, 4a, 5a$ to $6a,8a,10a$ and $9a,12a,15a$. Proof. Denote $\rightarrow$ be a triple reaching another. Then removing the scalar, we have \[(3,4,5)\rightarrow(5,12,13)\rightarrow(9,12,15)\rightarrow(9,40,41)\rightarrow (24,32,40)\rightarrow(10,24,26)\rightarrow(6,8,10)\]$\blacksquare$ Claim: We can get from $(3,4,5)$ to $(3p,4p,5p)$. Proof. Induct with base cases obvious. Then, start with \[(3p,4p,5p)\rightarrow (4p,2p^2-2,2p^2+2)\rightarrow \left(3\cdot \frac{p^2-1}{2},4\cdot\frac{p^2-1}{2},5\cdot \frac{p^2-1}{2}\right)\]This finishes as $\frac{p^2-1}{2}=(p-1)\frac{p+1}{2}$ both of which are less than $p$. $\blacksquare$ This finishes.
31.12.2023 02:20
Very enjoyable problem The idea is that we can do scaling, and because at every step we can pick any integer in the triple, this is almost all we need to do! Claim. From $(3, 4, 5)$, we can get to $(3k, 4k, 5k)$ for any $k$. Proof. This is a quirky induction, where we assume the result for all numbers less than $p$ for a given prime $p$ then show that $(3p, 4p, 5p)$ is attainable. This completes the induction, as for the next largest prime $q > p$, any number $k < q$ can be expressed as the product of powers of primes at most $p$ and hence is expressible. To complete the inductive step, just note that we can get to $(p^2-4, 4p, p^2+4)$ because $3 \mid (p-2)(p+2)$ and the rest of the factors of this are all less than $p$. Hence we can get to $(3p, 4p, 5p)$. $\blacksquare$ Now notice that in our original triple, there is a number that is a multiple of $3$, say $3k$. Then we may construct the triple $(3k, 4k, 5k)$ and notice that we can perform the exact algorithm we used to get from $(3, 4, 5) \to (3k, 4k, 5k)$ backward to get to $(3, 4, 5)$. This finishes by transitivity. $\blacksquare$
10.03.2024 00:39
orz @2above Say that $a \rightarrow b$ if it is possible to get from a Pythagorean triple containing $a$ to a Pythagorean triple containing $b$ using such a sequence. Clearly $a \rightarrow b$ if there is a Pythagorean triple containing $a, b$. Furthermore, $a \rightarrow b \iff b \rightarrow a$. Similarly, if $a \rightarrow b$, we know that $ak \rightarrow bk$ for any positive integer $k$ (this can be constructed by simply scaling all triples). We will now show that $3 \rightarrow k$ for all $k \geq 3$. Clearly $1, 2$ cannot be used in any Pythagorean triple, so this suffices. We will proceed by induction. Since $(3, 4, 5)$ is a Pythagorean triple, we have $3 \rightarrow 4, 5$. Furthermore, using the sequence \[ (3, 4, 5), (5, 12, 13), (9, 12, 15), (8, 15, 17), (6, 8, 10)\]we have that $3 \rightarrow 6$. Now, assume that $3 \rightarrow k$ for $k \leq n-1$. Consider the parity of $n$; if $n$ is even, then by the inductive hypothesis, $3 \rightarrow \frac{n}{2}$, so $6 \rightarrow n$. However, since $3 \rightarrow 6$, we have that $3 \rightarrow n$ and we are done. Now, assume that $n$ is odd. Using the triple $(n, \frac{n^2-1}{2}, \frac{n^2+1}{2})$, we know that $\frac{n^2-1}{2} \rightarrow n$. However, because $4 \rightarrow 3 \rightarrow n-1$ (by the inductive hypothesis), we have that $2(n+1) \rightarrow \frac{n^2-1}{2}$. Notice that $3 \rightarrow \frac{n+1}{2}$, so $12 \rightarrow 2(n+1)$. However, using triples $(3,4,5)$ and $(5, 12, 13)$ we have $3 \rightarrow 12$ (regardless of which inductive step we are on), so thus we are done.
22.05.2024 21:26
Man everyone saying its easy and the prob and took me 3 hr , how much mohs should this be?