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 $n 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.

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$.

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?