Online Course Discussion Forum

number theory help

Picture of Kevin Song
number theory help
by Kevin Song - Saturday, April 3, 2021, 3:37 PM

Hello, for 6.21 I don't know what to set as the contradiction and for 6.23 (c) I don't know how to prove it.

Picture of John Lensmire
Re: number theory help
by John Lensmire - Sunday, April 4, 2021, 11:48 AM

There are probably multiple ways to set up 6.21, but one way is to derive a contradiction using Bezout's Identity. Remember we've shown in the past that if we can find integers $X$ and $Y$ such that $X \cdot a + Y\cdot m = 1$, then in fact $\gcd(a, m) = 1$. Thus show that if $a^k \equiv 1 \pmod{m}$ for some $k$ you can use that to find such $X$ and $Y$.

For 6.23(c), it should be pretty easy. If $p$ divides $a$ then $a = c\cdot p$ for an integer $p$. What happens when you substitute this in?