Important! These are all exam-level problems. Do not attempt these problems without a solid foundation in the subject and use them for exam practice.
1. What is the invrese of 7 mod 48 (if it exists).
7. Notice that 7 *7 = 49 = 1 mod 48, which is the requirement for the inverse. 2. Let p, q be distinct prime numbers. Prove that pq-1 + qp-1 = 1 (mod pq)
Since p,q are unequal prime numbers, we know that gcd(p,q) = 1. So, we can apply fermat's little theorem both ways.
First, pq-1 = 1 (mod q) by Fermat's little theorem, and qp-1 = 0 (mod q), so their sums are equal to 1 (mod q).
Moreover, by a similar argument as above but by switching the roles of p and q, we get that pq-1 + qp-1 = 1 (mod p).
Now, we get that pq-1 + qp-1 - 1 is divisible by both p and q and, since p and q are relatively prime, we know that the above equation is divisble by pq. Now, we have that pq-1 + qp-1 - 1 = 0 (mod pq), and adding 1 to both sides of the equation gets us what we are trying to prove. 3. Disprove one of Euler's conjectures. Show that there is some positive integer n such that 1335 + 1105 + 845 + 275 = n5.
We're looking for some n, so it will be extremely useful to find some remainders n has after certain divisions.
To begin, let's look at the equation mod 5, keeping in mind Fermat's Little Theorem which claims that n5 is n (mod 5). Taking each value mod 5, we get 3 + 0 + 4 + 7 = n (mod 5), so 4 = n (mod 5). We now that n has a remainder of 4 when divided by 5.
Continuing, let's look at the equation mod 3. We get 1 + 2 + 0 + 0 = n5 (mod 3), so 0 = n (mod 3). We now know that n is perfectly divisible by 3.
By inspection, it n must be either 144 or 174. From there, we see that 175 is too large to satisfy the original equation, so we conclude that n = 144.