## Online Course Discussion Forum

### number theory help

number theory help

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.

Re: number theory help

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?