Online Course Discussion Forum

claire.seungyeon.lee@gmail.com

 
 
LensmireJohn的头像
Re: claire.seungyeon.lee@gmail.com
LensmireJohn - 2024年04月25日 Thursday 14:25
 

Some hints for the example questions (remember that these have sample solution ideas in the textbook as well that you can use to review as well).

  • 7.10 is actually very similar to 7.30. Note since gcd(a,pq)=1 then a is relatively prime with both a and b. Hence, by Fermat's Little Theorem we know that $a^{p-1} \equiv 1 \pmod{p}$ and $a^{q-1}\equiv 1\pmod{q}$. This implies that $a^k\equiv 1\pmod{p}$ and $a^k\equiv 1\pmod{q}$ (check this!). Then the fact from 7.30 above finishes the proof.
  • 6.10: We want to show there are infinitely many $n$ such that $n\cdot 2^n + 1 \equiv 0 \pmod{3}$. We know that $2^2\equiv 1\pmod{3}$, so actually as long as $n$ is even we know that $2^n\equiv 1\pmod{3}$. What happens if $n$ is even and $n\equiv -1\pmod{3}$?
  • 6.9: For questions like this, I think it's helpful to first look at an example prime (or multiple example primes) to start seeing a pattern for what happens. The screenshot below is from an old class with this problem, exploring when $p=13$: