1. ## Elementary # Theory

Hi guys, help me out with these, please!

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)

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

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

Thanks so much!

bEST WISHES,

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 $\displaystyle n<p$ it means there is an inverse of $\displaystyle n$ mod $\displaystyle p$. Let $\displaystyle x^{-1}$ by the modular inverse.

Therefore, $\displaystyle 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, $\displaystyle N\equiv (2n)(2n-1)...(n+1) (n!)^{-1} (\bmod p)$.

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

2. If gcd(a, 35)=1, show that a^12 = 1(mod 35)
$\displaystyle \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 $\displaystyle \text{lcm}(4,6)=12$.
Therefore $\displaystyle a^{12}\equiv 1(\bmod 35)$ for $\displaystyle \gcd(a,35)=1$.

3. If p and q are distinct primes, prove that
p^(q-1) + q^(p-1) = 1 (mod pq)
It is sufficient to prove,
$\displaystyle p^{q-1} + q^{p-1} \equiv 1(\bmod p)$
$\displaystyle p^{q-1} + q^{p-1} \equiv 1(\bmod q)$

Can you finish now?