Results 1 to 4 of 4

Math Help - Modulo arithmetic and factoring n

  1. #1
    Member
    Joined
    Oct 2007
    Posts
    89

    Modulo arithmetic and factoring n

    Hi again.
    Its getting late and its been a long day. I have one more question to study before I call it.
    Normally I would include my attempts on a question. But honestly, this time I do not think they are worth it. I feel lost on this one.
    Luckily I found the question on the web so I can refer to it easily

    http://www-users.math.umd.edu/~lcw/456F09.pdf
    It is #3.

    If this helps, this is listed under RSA questions.

    Even if someone can supply direction or hints, I can try looking at it again in the morning.
    Seeing that 1 there makes me want to say something related to Fermat's Little theorem, or at least a generalization of it.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by chrisc View Post
    Hi again.
    Its getting late and its been a long day. I have one more question to study before I call it.
    Normally I would include my attempts on a question. But honestly, this time I do not think they are worth it. I feel lost on this one.
    Luckily I found the question on the web so I can refer to it easily

    http://www-users.math.umd.edu/~lcw/456F09.pdf
    It is #3.

    If this helps, this is listed under RSA questions.

    Even if someone can supply direction or hints, I can try looking at it again in the morning.
    Seeing that 1 there makes me want to say something related to Fermat's Little theorem, or at least a generalization of it.


    (a) Since 1\neq k^2=2^{n-1} , if n were a prime we'd be contradicting flt;

    (b) With x\in\mathbb{Z}\,,\,\,xn+1=k^2=2^{n-1}\Longrightarrow xn=2^{n-1}-1 , and this is as far as I can get.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2007
    Posts
    89
    thank you. ill take a look in the morning and see what I can do with b.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Oct 2007
    Posts
    89
    (k^2) - 1 = 0modn
    (k+1)(k-1) = 0modn
    but k =/= + 1 or -1
    so there is a factor of n that divided (k+1) or (k-1)

    find the gcd of (k-1, n)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. modulo arithmetic
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: April 15th 2010, 08:10 AM
  2. Modulo Arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 4th 2009, 12:47 PM
  3. Modulo Arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 9th 2009, 04:56 AM
  4. modulo arithmetic
    Posted in the Math Topics Forum
    Replies: 7
    Last Post: December 31st 2007, 10:52 AM
  5. Modulo arithmetic
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 2nd 2007, 06:16 AM

Search Tags


/mathhelpforum @mathhelpforum