-
-
Notifications
You must be signed in to change notification settings - Fork 118
Open
Labels
Description
Description
I write my proofs in callouts on one of my blogs about math. The parser seems to miss some parts.
Input
Expected Output
> **PROOF**
>
> Part 1: Proof that there are atleast *one* solution
>
> 1. We have concluded that given $a$ and $b$, we can always find $m,n \in Z$ such that $\gcd(a,b) = am+bn$
> 2. Let $\gcd(a,b)=d$
> 3. $*d \mid c$* means $c = kd$ for some $k \in \Z$
> 4. We can rewrite $c=ax+by$ to $kd = ax+by$
> 5. We can always find $x,y \in \Z$ where $c=ax+by$ because from (1), we can always find $m, n \in Z$ such that $d = am+bn$ and
>
> $$
> \begin{split}
> c &= ax+by \\
> kd &= k(am+bn)
> \end{split}
>
> $$
>
> 6. Therefore we can find atleast one pair of $x$ and $y$ such that $c = ax+by$ if $\gcd(a,b) \mid c$ in the form of $x=km$ and $y=kn$ where $k=\frac{c}{\gcd(a,b)}$
>
> Part 2: Proof that there are *infinitely many* solutions
>
> 7. From (6), suppose $x'$ and $y'$ is also a solution to $c = ax+by$
> 8. Therefore we can write $ax+by=ax'+by'$
> 9. From (8) we can rearrange to $a(x-x')=b(y'-y)$
> 10. Let $a'=\frac{a}{d}$ and $b'=\frac{b}{d}$, $a'$ and $b'$ are coprime because of the following proof of contradiction
> 1. Assume $a'=\frac{a}{d}$ and $b'=\frac{b}{d}$ are not coprime and $d = \gcd(a,b)$
> 2. there is $e> 1$ such that $e=\gcd(a',b')$
> 3. Therefore $\frac{a'}{e}=\frac{a}{ed}$ is an integer, same goes with $\frac{b'}{e}=\frac{b}{ed}$
> 4. $ed > d$ since $e > 1$
> 5. Because there is an integer larger than $d$ that divides $a$ and $b$, $d \neq \gcd(a,b)$
> 6. Therefore (a) is wrong, $a'$ and $b'$ are coprime $\square$
> 11. From (9) and (10), $a'(x-x')=b'(y'-y)$
> 12. From (11)
>
> $$
> \begin{split}
> y'-y& =\frac{a'(x-x')}{b'}\\
> y' &=y + \frac{a'(x-x')}{b'}
> \end{split}
> $$
>
> 13. From (11)
>
> $$
> \begin{split}
> x-x'& =\frac{b'(y'-y)}{a'}\\
> x' &=x - \frac{b'(y'-y)}{a'}
> \end{split}
> $$
>
> 14. from (11), $\frac{(x-x')}{b'} = \frac{(y'-y)}{a'}$
> 15. $x'$ is an integer if $\frac{(y'-y)}{a'}$ is an integer because $x,b'\in \Z$
> 16. $\frac{(y'-y)}{a'}$ is an integer if $x'$ is an integer because of the following proof
> 1. Assume $a' \mid (y'-y)$
> 2. Therefore $(y'-y) = a'r$ for some $r \in \Z$
> 3. From (b), $by'-by = a'r$
> 4. Because $by' = c - ax'$ and $by = c - ax$, thus $ax-ax'= a'r$
> 5. Dividing by $a$, $x-x'= \frac{r}{d}$
> 6. From (e) rearranging to $d(x-x')= r$, the statement is true if $x'$ is an integer because $d,x,r \in \Z$
> 7. Therefore $\frac{(y'-y)}{a'} \in \Z$ if $x'\in \Z$ $\square$
> 17. Let $\frac{(x-x')}{b'} = \frac{(y'-y)}{a'} = t$
> 18. Rewrite $x'=x - \frac{tb}{d}$ and $y'= y + \frac{ta}{d}$
> 19. Therefore we can find infinitely many $x$ and $y$ such that $c = ax+by$ if $\gcd(a,b) \mid c$ in the form of $x=km - \frac{tb}{d}$ and $y=kn+ \frac{ta}{d}$ where $k=\frac{c}{\gcd(a,b)}$ for every integer $t \in \Z$ $\square$
Actual Output
> **PROOF**
> Part 1: Proof that there are atleast _one_ solution
>
> 1. We have concluded that given $a$ and $b$, we can always find $m,n \in Z$ such that $\gcd(a,b) = am+bn$
>
> 2. Let $\gcd(a,b)=d$
>
> 3. $d \mid c$ means $c = kd$ for some $k \in \Z$
>
> 4. We can rewrite $c=ax+by$ to $kd = ax+by$
>
> 5. We can always find $x,y \in \Z$ where $c=ax+by$ because from (1), we can always find $m, n \in Z$ such that $d = am+bn$ and
>
> 6. Therefore we can find atleast one pair of $x$ and $y$ such that $c = ax+by$ if $\gcd(a,b) \mid c$ in the form of $x=km$ and $y=kn$ where $k=\frac{c}{\gcd(a,b)}$
>
> Part 2: Proof that there are _infinitely many_ solutions
>
> 1. From (6), suppose $x'$ and $y'$ is also a solution to $c = ax+by$
>
> 2. Therefore we can write $ax+by=ax'+by'$
>
> 3. From (8) we can rearrange to $a(x-x')=b(y'-y)$
>
> 4. Let $a'=\frac{a}{d}$ and $b'=\frac{b}{d}$, $a'$ and $b'$ are coprime because of the following proof of contradiction
>
> 5. From (9) and (10), $a'(x-x')=b'(y'-y)$
>
> 6. From (11)
>
> 7. From (11)
>
> 8. from (11), $\frac{(x-x')}{b'} = \frac{(y'-y)}{a'}$
>
> 9. $x'$ is an integer if $\frac{(y'-y)}{a'}$ is an integer because $x,b'\in \Z$
>
> 10. $\frac{(y'-y)}{a'}$ is an integer if $x' $ is an integer because of the following proof
>
> 11. Let $ \frac{(x-x')}{b'} = \frac{(y'-y)}{a'} = t$
>
> 12. Rewrite $x'=x - \frac{tb}{d}$ and $y'= y + \frac{ta}{d}$
>
> 13. Therefore we can find infinitely many $x$ and $y$ such that $c = ax+by$ if $\gcd(a,b) \mid c$ in the form of $x=km - \frac{tb}{d}$ and $y=kn+ \frac{ta}{d}$ where $k=\frac{c}{\gcd(a,b)}$ for every integer $t \in \Z$ $\square$No pressure though, even the native notion export to md doesn't get it right
Metadata
Metadata
Assignees
Labels
Projects
Status
In Progress