Online Course Discussion Forum

Need help on II-A Number theory 7.28

 
 
Picture of Bober Yang
Need help on II-A Number theory 7.28
by Bober Yang - Sunday, 18 April 2021, 9:26 AM
 

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

Thanks 

 
Picture of Bober Yang
Re: Need help on II-A Number theory 7.28
by Bober Yang - Sunday, 18 April 2021, 9:36 AM
 

Also I need help on 7.30 too.

Picture of Areteem Professor
Re: Need help on II-A Number theory 7.28
by Areteem Professor - Monday, 19 April 2021, 1:15 PM
 

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}$?

Picture of Areteem Professor
Re: Need help on II-A Number theory 7.28
by Areteem Professor - Monday, 19 April 2021, 2:48 PM
 

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$?