MAT102 Prep 08B

• 1
  • What's a Linear Diophantine Equation?
• 2
  • $ax+by=c$ is a Linear Diophantine Equation
  • If $d=gcd(a,b)$ then $(x_0,y_0)$ is a solution to $ax+by=c$ iff $\frac{a}{d}x+\frac{b}{d}y=\frac{c}{d}$
  • Example:
    • $\begin{array}{c}a=3\\ b=6\end{array}$
      • $gcd(a,b)=3$
      • $3x+6y=3$ is valid
      • $3x+6y=9$ is valid
      • Divide all by $3$
      • $x+2y=3$
      • True
    • $\begin{array}{c}a=2\\ b=3\end{array}$
      • $gcd(a,b)=1$
      • $2x+3y=5$
    • True
  • $⟹$
    • Assume:
      • $d=gcd(a,b)$
      • $a{x}_0+b{y}_0=c$
    • Want to show that $\frac{a}{d}x+\frac{b}{d}y=\frac{c}{d}$
      • $a{x}_0+b{y}_0=c$
      • So $gcd(a,b)\mid a{x}_0+b{y}_0$
      • $d\mid a{x}_0+b{y}_0$
      • $c=dk=a{x}_0+b{y}_0$
      • $\frac{c}{d}=k=\frac{a}{d}{x}_0+\frac{b}{d}{y}_0$
      • True. However we only showed it for a single solution.
      • But this is what was asked to be shown.
  • $⟸$
    • Assume:
      • $d=gcd(a,b)$
      • $\frac{a}{d}{x}_0+\frac{b}{d}{y}_0=\frac{c}{d}$ is a solution
    • Want to show that $a{x}_0+b{y}_0=c$
      • $\frac{a}{d}{x}_0+\frac{b}{d}{y}_0=\frac{c}{d}$
      • If we multiply by the $gcd(a,b)$
      • $a{x}_0+b{y}_0=c$
      • Which is what we wanted
• 3
  • Let $a,b\in \mathbb{Z}$
  • $d=gcd(a,b)$
  • $ax+by=d$ has a solution $(x_0,y_0)$
  • What's a solution to $ax+by=4d$
  • I would assume $(4x_0,4y_0)$
  • $a{x}_0+b{y}_0=d$
  • $4a{x}_0+4b{y}_0=4d$
  • $a4x_0+b4y_0=4d$
  • $a(4x_0)+b(4y_0)=4d$
  • So solutions are $(4x_0,4y_0)$
• 4
  • $528x+756y=60$
  • $\{\begin{array}{ll}756& =528(1)+228\\ 528& =228(2)+72\\ 228& =72(3)+12\\ 72& =12(6)+0\end{array}$
  • $gcd(528,756)=12$
  • $528x+756y=12$
  • $228+72(-3)=12$
  • $756+528(-1)+(528+228(-2))(-3)=12$
  • $756+528(-1)+528(-3)+228(6)=12$
  • $756+528(-1)+528(-3)+(756+528(-1))(6)=12$
  • $756+528(-1)+528(-3)+756(6)+528(-6)=12$
  • $756(1+6)+528(-1-3-6)=12$
  • $756(7)+528(-10)=12$
  • $\begin{array}{c}x=7\\ y=-10\end{array}$
  • Since $\frac{60}{12}=5$
  • The multiplier of the solution by 3) is:
    • $5(756(7)+528(-10))=5(12)$
    • $756(35)+528(-50)=60$
  • General solutions
    • $x=-50+n\frac{756}{12}$
      • $x=-50+63n$
    • $y=35-n\frac{528}{12}$
      • $y=35-44n$
    • Test:
      • $528(-50+63(1))+756(35-44(1))=60$
      • $60=60$
• 5
  • $a,b,c\in \mathbb{Z}$
  • $a\mid bc$
  • $ak=bc,k\in \mathbb{Z}$
  • If $gcd(a,c)=1$ then $a\mid b$
    • Assume hypothesis
      • $gcd(a,c)=1$
      • $k,\ell \in \mathbb{Z}$
      • $a\mid bc$
        • $ak=bc$
      • $a{x}_0+c{y}_0=1$ has the solution
    • Want to prove
      • $a\mid b$
      • $a\ell =b$
    • Proof:
      • $a{x}_0+c{y}_0=1$
      • $ba{x}_0+bc{y}_0=b$
      • $a\ell =ba{x}_0+bc{y}_0$
      • $a\ell =b(\underset{\in \mathbb{Z}}{\underbrace{a{x}_0+c{y}_0}})$
      • Proven
  • $a\mid b$ or $a\mid c$
    • False
  • $a$ is prime then $a\mid b$ or $a\mid c$ but cannot divide both
    • $a\mid bc$
      • $ak=bc$
    • $a$ is prime
    • So then $gcd(a,b)=1$ and $gcd(a,c)=1$
    • $a{x}_0+b{y}_0=1$
    • $a{x}_0+c{y}_0=1$
    • Without loss of generality
    • if $a\mid b$, show that $a\nmid c$
    • $a\mid b$
      • $a\ell =b$
    • $a\nmid c$
      • Suppose there were solutions to $a\mid c$
      • $aj=c$
      • $ak=bc$
      • $ak=a\ell aj$
      • $ak=a^2\ell j$
      • $ak=a^2\ell j$
      • $a{x}_0+b{y}_0=1$
      • $a{x}_0+c{y}_0=1$
      • $a{x}_0+b{y}_0=a{x}_0+c{y}_0$
      • $b{y}_0=c{y}_0$
      • $b=c$
      • $aj=a\ell$
      • $ak=bc$
  • If $a\nmid b$ and $a\nmid c$ this means that $a$ is composite
• 6
  • $p_1,p_2,p_3$ are distinct primes
  • $n=3$
  • $p_1^{a_1}{p}_2^{a_2}\dots p_n^{a_n}=p_1^{b_1}{p}_2^{b_2}\dots p_n^{b_n}$
  • What's true?:
    • $a_i=\pm b_i$ for $i=1,2,3$
      • $p_1^{a_1}{p}_2^{a_2}\dots p_n^{a_n}=p_1^{\pm b_1}{p}_2^{\pm b_2}\dots p_n^{\pm b_n}$
      • Well it's not $\pm$ it would be either all $+$s, or 2 $-$s
    • $a_1=a_2=a_3$ and $b_1=b_2=b_3$
      • Not necessarily true
      • $a_1=2$
      • $a_2=3$
      • $a_3=5$
      • $b_1=2$
      • $b_2=3$
      • $b_3=5$
      • $2^{a_1}{3}^{a_2}{5}^{a_3}=2^{b_1}{3}^{b_2}{5}^{b_3}$
    • $gcd(p_1^{a_1}{p}_2^{a_2}\dots p_n^{a_n},p_1^{b_1}{p}_2^{b_2}\dots p_n^{b_n})=p_1^{min(a_1,b_1)}{p}_2^{min(a_1,b_1)}\dots p_n^{min(a_1,b_1)}$
      • True
    • $a_i=b_i$ for $i=1,2,3$
      • This is true and is a way to have equal numbers.
• 7
  • $S=\{p_1,p_2,\dots ,p_n\}$ is primes, and finite.
  • $P=p_1{p}_2\dots p_n+1$
    • $P$ is prime
      • To prove this we can say that $gcd(P,3)=1$ to show they're co-prime.