Online Course Discussion Forum

Help

 
 
Picture of David Tang
Help
by David Tang - Saturday, 11 April 2020, 10:10 AM
 

21-24, and 29B please. Thanks.

-DAVID TANG

 
Picture of David Reynoso
Re: Help
by David Reynoso - Monday, 13 April 2020, 1:15 PM
 

This is for Math Challenge II-B week 6, right?

Here are some hints:

- 21: Assume $a^k \equiv 1 \pmod{m}$. From here try to find integers $b$ and $c$, with $\gcd(b,c) = 1$, such that $b\cdot a + c\cdot m = 1$. Using Bezout's Identity, this would contradict the fact that $\gcd(a.m) > 1$.

- 22: By the division algorithm, there exist integers $q$ and $r$, with $0\leq r < j$, such that $k = q\cdot j + r$. Use this and the definition of $j$  to prove that $r$ must be equal to $0$, and thus $j \mid k$. 

- 23.a: What happens if we multiply by $a$ on $a^{p-1} \equiv 1 \pmod{p}$?

- 23.b: $p \mid a^p - a$ is equivalent to $a^p - a \equiv 0 \pmod{p}$. How can we get from there to $a^{p-1} \equiv 1 \pmod{p}$?

- 24: Here we want to verify that Wilson's Theorem is true for  $p = 2, 3, 5, 7, 11$, so we want to plug in those values of $p$ in $p \mid (p-1)! + 1$ and check that the statement is true.

- 29.b: Try plugging in small values of $p$ that are not of the form $p - 4k + 1$.

Picture of David Tang
Re: Help
by David Tang - Thursday, 16 April 2020, 3:43 PM
 
Thanks.