Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By Sarasij

Math Help - Help in some suggested questions about congruences, Fermat theorem (& maybe Wilson's)

  1. #1
    Newbie
    Joined
    Jun 2012
    From
    Federal District, Brazil
    Posts
    2

    Help in some suggested questions about congruences, Fermat theorem (& maybe Wilson's)

    Hi people! That's my first time here in this forum, and I want to share with you some doubts.
    My teacher of number's theorie suggested about 40 exercises about congruences, and I'm having trouble in some (5) of them.

    There are the exercises:

    EDIT: NOTATION: (a,b) is the greatest common divisor of a and b; N for Naturals, Z for Integers and P for primes; \phi (a) is the Euler Totient of a.

    1st) If p, q \in P and p \neq q, so p^{q-1} + q^{p-1} \equiv 1 \pmod{p.q}.
    -Observation: I think one problem is that I don't know how to create an useful relation in mod pq using relations on mod p and mod q. The only way that I know is the way that goes with the property: If a \equiv b (mod n), so a.c \equiv b.c \pmod{c.m} .

    2nd) This second exercise is an generalization of the previous one (they are presented in this order).
    If a, b \in N and (a,b) = 1 , so a^{\phi (b)} + b^{\phi (a)} \equiv 1 \pmod{a.b}

    3rd) The third problem is how to proof that  42|a^7 - a, \forall a \in Z.

    4th) Exercise: If p, q \in P, with p \neq q, are related as follows: a^p \equiv a \pmod{q} and a^q \equiv a \pmod{p}, so a^{pq} \equiv a \pmod{pq}.
    -Obs.: I think the observation posted in the first exercise will affect this one.

    5th) If a \in Z and p,q \in P, with p \neq q, so p.q | a^{p+q} - a^{p+1} - a^{q+1} + a^2.


    I hope you can help me, any help (or try to) is very welcome!

    Thanks,
    Rodrigo.
    Last edited by Rodrigomkt; June 11th 2012 at 04:30 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member Sarasij's Avatar
    Joined
    Jun 2011
    From
    India
    Posts
    42
    Thanks
    2

    Re: Help in some suggested questions about congruences, Fermat theorem (& maybe Wilso



    ------------------------------------------------------------------------------------------------------------------
    Solution to the third problem:


    a7-1

    = a(a6-1)

    = a(a3+1)(a3-1)

    = a(a+1)(a-1)(a2+a+1)(a2-a+1)

    Clearly a(a+1) is divisible by 2 and a(a+1)(a-1) is divisible by 3.

    Now the hard part is to show 7|(a7-1). When divided by 7 the possible remainders are 1,2,3,...,6.

    If a≡1(mod 7) then a3≡1(mod 7).

    If a≡2(mod 7) then a3≡8(mod 7)≡1(mod 7)

    If a≡3(mod 7) then a3≡27(mod 7)≡-1(mod 7) i.e. a3+1≡0(mod 7)

    If a≡4(mod 7) then a3≡64(mod 7)≡1(mod 7)

    If a≡5(mod 7) then a3≡125(mod 7)≡-1(mod 7) i.e. a3+1≡0(mod 7)

    If a≡6(mod 7) then a≡6(mod 7)≡-1(mod 7) i.e. a+1≡0(mod 7)

    Therefore, the expression (a7-1) is always divisible by 3 primes 2 , 3 and 7. So its divisible by 2x3x7=42 for all integers a.
    --------------------------------------------------------------------------------------------------------------------------------
    Solution to the fourth problem:

    p and q are primes , p and q are distinct and ap ≡ a (mod q) and aq ≡ a (mod p).

    By Fermat's Little Theorem we know ap ≡ a (mod p) and aq ≡ a (mod q).

    Therefore, ap ≡ a (mod q) => (ap)q ≡ aq (mod q) => apq ≡ aq (mod q) ≡ a (mod q)

    Similarly aq ≡ a (mod p) => apq ≡ ap (mod q) ≡ a (mod q)

    i.e ( apq - a) is divisible by both primes p and q where p and q are distinct. This implies that ( apq - a) is divisible by (pq) also.

    So ( apq - a) ≡ 0 (mod pq) => apq ≡ a (mod pq).
    --------------------------------------------------------------------------------------------------------------------------------

    Solution to the 5th problem:

    p and q are primes , p and q are distinct.

    Now

    ap+q - ap+1 - aq+1 + a2

    = (ap - a )(aq - a)

    = pK1 . qK2 for some integers K1 and K2[By Fermat's Little Theorem]

    = (pq).K where K=K1.K2

    Therefore pq | (ap+q - ap+1 - aq+1 + a2)
    --------------------------------------------------------------------------------------------------------------------------------
    Last edited by Sarasij; June 12th 2012 at 03:11 AM.
    Thanks from Rodrigomkt
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2012
    From
    Federal District, Brazil
    Posts
    2

    Re: Help in some suggested questions about congruences, Fermat theorem (& maybe Wilso

    Quote Originally Posted by Sarasij View Post
    [B]
    --------------------------------------------------------------------------------------------------------------------------------
    Solution to the fourth problem:

    p and q are primes , p and q are distinct and ap ≡ a (mod q) and aq ≡ a (mod p).

    By Fermat's Little Theorem we know ap ≡ a (mod p) and aq ≡ a (mod q).

    Therefore, ap ≡ a (mod q) => (ap)q ≡ aq (mod q) => apq ≡ aq (mod q) ≡ a (mod q)

    Similarly aq ≡ a (mod p) => apq ≡ ap (mod q) ≡ a (mod q)

    i.e ( apq - a) is divisible by both primes p and q where p and q are distinct. This implies that ( apq - a) is divisible by (pq) also.

    So ( apq - a) ≡ 0 (mod pq) => apq ≡ a (mod pq).
    Thanks for all these exercise solutions Sarasij!
    Specially for the 4th exercise solution, because of the property that you showed me (underlined).
    With this property I solved the 1st and 2nd exercises easily.

    Here's a more general version of the property: Be a,b,k \in Z, if a|k and b|k and (a,b)=1, so a.b|k .

    Thanks for all,
    Rodrigo
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member Sarasij's Avatar
    Joined
    Jun 2011
    From
    India
    Posts
    42
    Thanks
    2

    Re: Help in some suggested questions about congruences, Fermat theorem (& maybe Wilso

    Quote Originally Posted by Rodrigomkt View Post
    Thanks for all these exercise solutions Sarasij!
    Specially for the 4th exercise solution, because of the property that you showed me (underlined).
    With this property I solved the 1st and 2nd exercises easily.

    Here's a more general version of the property: Be a,b,k \in Z, if a|k and b|k and (a,b)=1, so a.b|k .

    Thanks for all,
    Rodrigo
    You are welcome...if you liked my solutions then I request you to give thanks to my user account by clicking the "Thanks" shown at the end of my replies.(Of course this is not mandatory,but in case if you want to...)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Wilson's theorem proofing questions?
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 9th 2012, 04:41 PM
  2. Fermat, Congruences, the CRT, and an exam question
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: July 24th 2011, 09:17 PM
  3. Applying Fermat and Wilson's Theorem
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 21st 2010, 07:06 PM
  4. Two problems with Fermat and Wilson
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 5th 2009, 03:48 PM
  5. More on Wilson and Fermat
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 23rd 2008, 08:07 PM

Search Tags


/mathhelpforum @mathhelpforum