Online Course Discussion Forum
MCII-B Number Theory 6.28, 6.30
I tried something similar to Example 6.8 for Question 6.28, but I'm still stuck. Same thing for 6.30...how could I start these questions?
6.28 asks to find all primes $p$ such that $p\mid 2^{2p}+1$. First of all, can you find one such prime? Then, note that $2^{2p}=4^p$.
6.30: we want to find $n$ such that $n2^n \equiv -1\pmod{p}$. You can consider $n$ and $2^n$ separately: perhaps one of them can be $-1$ mod $p$, and the other $1$ mod $p$ at the same time.
Hint for 6.28: To at least narrow down options and get some restrictions, note 2^(2p) = 4^p. What can we say about 4^p if we look (mod 5)? This can help. (I gave this on Discord as well.)
Expanding on the hint for 6.30, think of $n\cdot 2^n + 1$ as $A\cdot B + 1$ (so of course $A = n$ and $B = 2^n$). The hint is implying we want to have $A \equiv -1 \pmod{p}$, $B\equiv 1 \pmod{p}$, and then $n\cdot 2^n + 1 \equiv 0 \pmod{p}$.
Hint: By Fermat's Little Theorem we know $2^{p-1} \equiv 1\pmod{p}$. Thus, we actually know that raising 2 to any multiple of (p-1) will be equivalent to 1 (mod p). This can help make sure B is 1 (mod p). How can we still keep B to be 1 (mod p) and also ensure A is -1 (mod p)?
For 6.28, I know that 5 is a prime that works, but why do we do 4^p mod 5 and not mod any other prime?
For 6.30, A or n would have to be xp-1, where x is some positive integer, which is congruent to -1 (mod p), but B would be 2^(ap-1)=1 (mod p)...I'm not sure how this is helpful...
Reply to both at once.
For 6.28, we do know that $4^p \equiv 4 \pmod{p}$ for any prime, right? But then how can $4^p + 1 \equiv 0 \pmod{p}$ if $p > 5$?
For 6.30, you're on the right track, $A$ needs to be one less than a multiple of $p$, so really any $A\equiv -1 \pmod{p}$ should work. Hint here for A: (-1) raised to an odd power is always $\equiv -1 \pmod{p}$. Hint for B: Consider exponents that are powers of (p-1).
Social networks