Elementary # Theory

Quote:

Originally Posted by felixmcgrady

1. if p is a prime satisfying n<p<2n, show that
2n(2n-1).....(n+1) / n(n-1)(n-2).....1 = 0(mod p)

Since $n<p$ it means there is an inverse of $n$ mod $p$ . Let $x^{-1}$ by the modular inverse.

Therefore, $N=\frac{2n(2n-1)...(2)}{n(n-1)...(2)(1)} \equiv (2n)(2n-1)...(n+1)(n)^{-1}(n-1)^{-1} ... 2^{-1} (\bmod p)$

Therefore, $N\equiv (2n)(2n-1)...(n+1) (n!)^{-1} (\bmod p)$ .

But $p$ divides $(2n)(2n-1)...(2)(1)$ since $p<2n$ . Therfore, $p|(n+1)...(2n)$ since $p\not | (n!)$ . There is a factor of $p$ and therefore it is congruent to 0 mod p.

Quote:

2. If gcd(a, 35)=1, show that a^12 = 1(mod 35)

$\mathbb{Z}_{35}^{\times} \simeq \mathbb{Z}_5^{\times} \times \mathbb{Z}_7^{\times} \simeq \mathbb{Z}_4 \times \mathbb{Z}_6$ .
The exponent of this group is $\text{lcm}(4,6)=12$ .
Therefore $a^{12}\equiv 1(\bmod 35)$ for $\gcd(a,35)=1$ .

Quote:

3. If p and q are distinct primes, prove that
p^(q-1) + q^(p-1) = 1 (mod pq)

It is sufficient to prove,
$p^{q-1} + q^{p-1} \equiv 1(\bmod p)$
$p^{q-1} + q^{p-1} \equiv 1(\bmod q)$

Can you finish now?