Results 1 to 5 of 5

Math Help - exercise in Number Theory

  1. #1
    Newbie
    Joined
    May 2008
    Posts
    4

    exercise in Number Theory

    This exercise has also been posted yesterday at the cryptography help thread. Since my deadline for delivery has approached earlier I decided to move it here. I don't believe it is related to cryptography as much as Number's Theory.

    Prove that the following is true:

    11^n + 5^n = 0 (mod7) when n = 3 (mod6)
    Hint: You can use (it is proven) that 11^3 = 1 (mod3) and 5^3 = -1 (mod3)

    Thanks in advance for your time and help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    Quote Originally Posted by closebelow View Post
    Hint: You can use (it is proven) that 11^3 = 1 (mod3) and 5^3 = -1 (mod3)

    Are you sure that 11^3=1 \mod 3 ?

    Because it would mean that 11^3-1 is a multiple of 3.
    But 11^3=1331 and 1331-1=1330, which is obviously not a multiple of 3
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by closebelow View Post
    This exercise has also been posted yesterday at the cryptography help thread. Since my deadline for delivery has approached earlier I decided to move it here. I don't believe it is related to cryptography as much as Number's Theory.

    Prove that the following is true:

    11^n + 5^n = 0 (mod7) when n = 3 (mod6)
    Hint: You can use (it is proven) that 11^3 = 1 (mod3) and 5^3 = -1 (mod3)

    Thanks in advance for your time and help.

    Ya moo, he is wrong. It should actually read:
    11^3 = 1 (mod7) and 5^3 = -1 (mod7)


    n = 3 (mod6) means 6|(n-3). But this means 3|n. Thus n = 3k where k is an integer.
    So 6|3(k-1) and thus 2|k-1 and therefore k is odd.

    Now since k is odd,

    11^n + 5^n = 11^3k + 5^3k = 1 + (-1)^k = 1 + -1 = 0 (mod7)






    Aliter:Induction:
    For n=1, follows from hint.
    Assume for n and prove for n+6

    Read the below line modulo 7,

    11^(n+6) + 5^(n+6) = 11^n 11^6 + 5^n 5^6 = 11^n (11^3)^2 + 5^n (5^3)^2 = 11^n (1)^2 + 5^n (-1)^2 = 11^n + 5^n

    But 11^n + 5^n mod 7 = 0, by induction hypothesis
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Ah, I was wondering why he was given mod 3's.

    Here's another approach :

    n=3 \mod 6

    This means that n=3+6k \ , k \in \mathbb{Z}

    \implies 11^n+5^n=11^3 \cdot (11^6)^k+5^3 \cdot (5^6)^k, by using the power rules ! **

    From Fermat's little theorem, we know that 11^6=1 \mod 7 and 5^6=1 \mod 7

    Therefore :

    11^n+5^n=11^3 \cdot (11^6)^k+5^3 \cdot (5^6)^k=11^3 \cdot 1^k+5^3 \cdot 1^k \mod 7

    11^n+5^n=11^3+5^3 \mod 7

    11^n+5^n=1-1 \mod 7

    QED.

    --------------

    ** as a recall :

    a^{b+c}=a^b \cdot a^c

    a^{mn}=(a^m)^n=(a^n)^m
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2008
    Posts
    4
    Hello guys and thanks for your help

    I'm sorry but the exercise as given is like this:

    Prove that the following is true: 11^n + 5^n = 0 (mod7) when n = 3 (mod6)
    Hint: You can use (it is proven) that 11^3 = 1 (mod3) and 5^3 = -1 (mod3)

    I'm currently reading your posts and I see your point, the exercise has definitely some fault. Thanks for your time and effort!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Textbooks on Galois Theory and Algebraic Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: July 8th 2011, 06:09 PM
  2. Measure Theory exercise...
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: May 11th 2009, 06:58 PM
  3. Replies: 2
    Last Post: December 18th 2008, 05:28 PM
  4. Cardinal number exercise
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: March 29th 2008, 06:02 AM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 17th 2006, 08:11 PM

Search Tags


/mathhelpforum @mathhelpforum