Results 1 to 2 of 2

Math Help - Elementary # Theory

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    39

    Smile 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,
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by felixmcgrady View Post
    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.

    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?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Elementary # theory
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 29th 2008, 09:06 AM
  2. elementary # theory
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 10th 2008, 05:51 AM
  3. Elementary # Theory
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 4th 2008, 05:37 AM
  4. Elementary # Theory
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 2nd 2008, 10:13 PM
  5. Elementary # Theory
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 1st 2008, 02:55 AM

Search Tags


/mathhelpforum @mathhelpforum