Results 1 to 7 of 7

Math Help - modular arithmetic and prime number

  1. #1
    Newbie
    Joined
    Jun 2012
    From
    Singapore
    Posts
    2

    modular arithmetic and prime number

    Hi,
    I have spent hours on this question:- For what positive integers n is 4n+ 7 2n+1 + 103n-1 aprime number?.... no clue on how to tackle it. I appreciate if someonecould help.
    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: modular arithmetic and prime number

    Quote Originally Posted by snseng View Post
    Hi,
    I have spent hours on this question:- For what positive integers n is 4n+ 7 2n+1 + 103n-1 aprime number?.... no clue on how to tackle it. I appreciate if someonecould help.
    I claim that the sum S = 4n + 72n+1 + 103n-1 is always divisible by 3 for any n and is not a prime for all natural number n.

    Proof:
    4n is of the form 3x + 1 i.e. 4n = 3x + 1
    72n+1 = (3x2 + 1)2n+1 = 3y + 1 &
    103n-1 = (3x3 + 1)3n-1 = 3z + 1

    So S = (3x+1) + (3y+1) + (3z+1) = 3(x + y + z + 1) => 3|S.

    Hence proved.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2012
    From
    Singapore
    Posts
    2

    Re: modular arithmetic and prime number

    Hi Sarasij,

    Thanks so much for your speedy response.

    In fact, I got the similar outcome that the expression is dividable by 3. This question was given by the school to my kid. I have spent a morning to learn from scratch about Modular Arithmetic and not much confidence on it. At the same time, I do not expect such a 'naughty' question as I presumed 'n' shall exist some positive integers... keep on trying. Ha Ha, interesting!

    Have a good night/day.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: modular arithmetic and prime number

    modular arithmetic is the perfect tool for investigating things concerning divisibilty (and thus about primes, for example).

    the nice thing about it is that:

    a (mod n) + b (mod n) = a+b (mod n), and:
    (a mod n)(b mod n) = ab (mod n)

    so it doesn't matter if you reduce mod n before or after adding (or multiplying).

    so we have:

    4 = 1 (mod 3)
    7 = 1 (mod 3)
    10 = 1 (mod 3)

    therefore:

    4n + 72n+1 + 103n-1

    ≡ (1)n + (1)2n+1 + (1)3n-1 (mod 3)

    ≡ 1 + 1 + 1 (mod 3)

    ≡ 0 (mod 3), thus we have 4n + 72n+1 + 103n-1 is divisible by 3.

    one can also attempt an induction proof, that 4n + 72n+1 + 103n-1 is divisible by 3 for all natural numbers n.

    base case: n = 1:

    4 + 73 + 102 = 4 + 343 + 100 = 447 = 3*149.

    assume that:

    4k + 72k+1 + 103k-1 = 3x, for some positive integer x.

    then:

    4k+1 + 72k+3 + 103k+2 =

    (4k+1 - 4k) + (72k+3 - 72k+1) + (103k+2 - 103k-1) + 4k + 72k+1 + 103k-1

    = 4k(4 - 1) + 72k+1(72 - 1) + 103k-1(103 - 1) + 3x <---by our induction hypothesis

    = 4k(3) + 72k+1(48) + 103k-1(999) + 3x

    = 3[4k + (72k+1)(16) + (103k-1)(333)] + 3x

    = 3y + 3x = 3(y + x), for y = 4k + (72k+1)(16) + (103k-1)(333)

    and is therefore true for all n.
    Follow Math Help Forum on Facebook and Google+

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

    Re: modular arithmetic and prime number

    Quote Originally Posted by Deveno View Post
    modular arithmetic is the perfect tool for investigating things concerning divisibilty (and thus about primes, for example).

    the nice thing about it is that:

    a (mod n) + b (mod n) = a+b (mod n), and:
    (a mod n)(b mod n) = ab (mod n)

    so it doesn't matter if you reduce mod n before or after adding (or multiplying).

    so we have:

    4 = 1 (mod 3)
    7 = 1 (mod 3)
    10 = 1 (mod 3)

    therefore:

    4n + 72n+1 + 103n-1

    ≡ (1)n + (1)2n+1 + (1)3n-1 (mod 3)

    ≡ 1 + 1 + 1 (mod 3)

    ≡ 0 (mod 3), thus we have 4n + 72n+1 + 103n-1 is divisible by 3.

    one can also attempt an induction proof, that 4n + 72n+1 + 103n-1 is divisible by 3 for all natural numbers n.

    base case: n = 1:

    4 + 73 + 102 = 4 + 343 + 100 = 447 = 3*149.

    assume that:

    4k + 72k+1 + 103k-1 = 3x, for some positive integer x.

    then:

    4k+1 + 72k+3 + 103k+2 =

    (4k+1 - 4k) + (72k+3 - 72k+1) + (103k+2 - 103k-1) + 4k + 72k+1 + 103k-1

    = 4k(4 - 1) + 72k+1(72 - 1) + 103k-1(103 - 1) + 3x <---by our induction hypothesis

    = 4k(3) + 72k+1(48) + 103k-1(999) + 3x

    = 3[4k + (72k+1)(16) + (103k-1)(333)] + 3x

    = 3y + 3x = 3(y + x), for y = 4k + (72k+1)(16) + (103k-1)(333)

    and is therefore true for all n.

    Hi Devono,
    Actually I don't know how to write the congruent modulo sign here. So that's why I explained the logic to him using only division algorithm. But it becomes much more simpler if I use this operator(congruent modulo). Can you please tell me how to use it in this forum?
    I also admire your inductive trick based proof.
    Last edited by Sarasij; June 6th 2012 at 09:16 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: modular arithmetic and prime number

    there are two ways:

    1. Use a unicode-based symbol (which you could do by copying and pasting this: ≡)

    2. use latex (on this forum the latex tag is [tex ][/tex] (but without the space). in latex, the code for the modulus congruence sign is: \equiv such as:

    2 \equiv 6\ \text{mod }4

    what is inside the latex tags is:

    2 \equiv 6\ \text{mod }4
    Follow Math Help Forum on Facebook and Google+

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

    Re: modular arithmetic and prime number

    Quote Originally Posted by Deveno View Post
    there are two ways:

    1. Use a unicode-based symbol (which you could do by copying and pasting this: ≡)

    2. use latex (on this forum the latex tag is [tex ][/tex] (but without the space). in latex, the code for the modulus congruence sign is: \equiv such as:

    2 \equiv 6\ \text{mod }4

    what is inside the latex tags is:

    2 \equiv 6\ \text{mod }4
    Thank you so much Devono.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 8th 2011, 11:45 AM
  2. Modular arithmetic.
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 10th 2011, 06:21 PM
  3. Modular Arithmetic
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 28th 2010, 04:54 AM
  4. modular arithmetic
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: March 18th 2010, 09:33 AM
  5. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 13th 2008, 04:17 PM

Search Tags


/mathhelpforum @mathhelpforum