Areteem: claire.seungyeon.lee@gmail.com

Online Course Discussion Forum

We didn't do Problem 6.9, 6.10, 7.10 in class so could you explain how to solve it?

I need help with 7.22(a), 7.22(b), 7.26(c), 7.28, 7.29, 7.30. Could you also explain how to do these?

Thank you

Let me start with some hints for the ones from this week's homework:

7.22(a)+(b): You should have a general formula for $\phi(n)$ involving the prime factorization of $n$ in the beginning of chapter 7 in the textbook. We can still use that formula here, just the answer will be in terms of the variables p, q, k, and l. (For example, in (c) you're basically doing (b) with p=2, k=4, q=5, and l=2.)
As a hint for 7.26(c), remember you can also use negative numbers. $6\cdot 11 \equiv -2 \pmod{17}$, so what times $-2$ gives 1 more than a multiple of $17$?
Thinking of negative numbers can also be helpful for 7.28. If $x \equiv k\pmod{k+1}$, how does $x$ relate to a multiple of $k+1$?
7.29: Start by finding a pattern for powers of $9$ modulo $7$. From there you should be able to find out where in the pattern you are for the exponent $9^9$.
7.30: Let me give this fact as a hint: Knowing that gcd(m,n)=1, by the Chinese Remainder if $A+B\equiv 1 \pmod{n}$ and $A+B\equiv 1\pmod{m}$ then $A+B\equiv 1 \pmod{mn}$.

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