Selected solutions to PS 4

Problem 1

Consider for instance n=m³ for m even. Then n²+1=m⁶+1=(m²+1)(m⁴-m²+1).

Problem 2a

All these follow in a straightforward manner from FLT. For example $3^{96} \equiv 1 (mod 97)$, $8^{10} \equiv 1 (mod 11)$, which implies $8^{102} \equiv (8^{10})^{10} \times 8^2 \equiv 8^2 \equiv 9 (mod 11)$. $(-5)^{12} \equiv 1 (mod 13)$, thus $(-5)^{12002} \equiv (-5)^2 \equiv 12 (mod 13)$.

Problem 3

$(p-1)^{p-1} - 1 \equiv 0 (mod p)$ by Fermat's Little Theorem. $(p-1)! + 1 \equiv 0 (mod p)$ by Wilson's theorem. Since each of the two factors is divisible by p, the product is divisible by p².

Problem 4a

$x \equiv 0 (mod 3)$ is not a solution, therefore we can assume gcd(x,3)=1, and use FLT $x^2 \equiv 1 (mod 3)$. Thus, $x^{780} \equiv (x^{2})^{390} \equiv 1 (mod 3)$, and $x^{613} \equiv (x^{2})^{306} x \equiv x (mod 3)$. The equation thus reduces to $x+2 \equiv 1 (mod 3)$, and so the only solution is $x \equiv 2 (mod 3)$.

Problem 5

Lagrange's Theorem tells us that an equation of degree 5 modulo a prime has at most 5 solutions. Plugging in 0, 1, 2, p-2, p-1 we see that all of these are solutions, and since we can have at most 5, they have to be all of the solutions.

For 5b, experiment and find 5 distinct solutions that work (mod p) for any p > 7.

Problem 6

Observe that since 7 divides 147, any solution (mod 147) will be a solution (mod 7). It therefore suffices to show that the equation has no solutions (mod 7). (mod 7), the equation reduces to

$$x^6 + 1 \equiv 0 (mod 7)$$

Now, $x \equiv 0 (mod 7)$ is not a solution, so we can assume by FLT that $x^6 \equiv 1 (mod 7)$, but this implies that the left hand side $\equiv 2 (mod 7)$, so the equation has no solutions (mod 7), and therefore none (mod 147).

Problem 7

The solutions (mod 100) are 1, 81, 61, 41, 21, 33.