## Online Course Discussion Forum

### Need help on II-A Number theory 7.28

Need help on II-A Number theory 7.28

I am not sure where to start this problem. If anyone can help me it would be great.

Thanks

Re: Need help on II-A Number theory 7.28

Also I need help on 7.30 too.

Re: Need help on II-A Number theory 7.28

Recall that the extension of Fermat's Little Theorem says that $a^{\phi(n)} \equiv 1 \pmod{n}$ if $\gcd(a,n) = 1$.

What can you say about $m^{\phi(n)} + n^{\phi(m)} \pmod{n}$ and $m^{\phi(n)} + n^{\phi(m)} \pmod{m}$?

Re: Need help on II-A Number theory 7.28

In example 8 we found all values of $x$ such that $x \equiv 1 \pmod{4}$, $x \equiv 2 \pmod{5}$, and $x \equiv 3 \pmod{6}$, even though the Chinese Reminder Theorem does not guarantee that such solutions will exist since $\gcd(4,6)\neq 1$.

Here we want to do the same, but a bit more general.

For example, for $M = 10$ we would like to find $x$ such that \begin{aligned} x &\equiv 1 \pmod{4} \\ x &\equiv 2 \pmod{5} \\ x &\equiv 3 \pmod{6} \\ & \vdots \\ x &\equiv 9 \pmod{12} \\ x &\equiv 10 \pmod{13}. \\ \end{aligned} This means \begin{aligned} x + 3 &\equiv 0 \pmod{4} \\ x + 3 &\equiv 0 \pmod{5} \\ x + 3 &\equiv 0 \pmod{6} \\ & \vdots \\ x + 3 &\equiv 0 \pmod{12} \\ x + 3 &\equiv 0 \pmod{13}. \\ \end{aligned} So $x + 3$ is a multiple of all $4, \dots, 13$, thus one solution is $x = \text{lcm}(4,\dots,13) - 3$.

What can we do then for a general $M$?