Results 1 to 3 of 3

Math Help - How many integers n are there such that 0 ≤ n ≤ 720 and n^2 ≡ 1 (mod 720)?

  1. #1
    Junior Member
    Joined
    Jul 2010
    From
    NJ
    Posts
    68

    How many integers n are there such that 0 ≤ n ≤ 720 and n^2 ≡ 1 (mod 720)?

    This is my approach, but I think I'm wrong.

    How many integers n are there such that 0 ≤ n ≤ 720 and n^2 ≡ 1 (mod 720)?

    So, I observed 720 = 6!, so this must mean that:
    n^2 ≡ 1 mod 6, and
    n^2 ≡ 1 mod 5, and
    n^2 ≡ 1 mod 4, and
    n^2 ≡ 1 mod 3, and
    n^2 ≡ 1 mod 2.

    But here the modulos aren't relatively prime, so I prime factorized 720 and did:
    n^2 ≡ 1 mod 16, and
    n^2 ≡ 1 mod 9, and
    n^2 ≡ 1 mod 5.
    (Since 16*9*5 = 720)

    Taking the modular square root, we observe that:
    n ≡ 1 mod 16 OR n ≡ 15 mod 16, and
    n ≡ 1 mod 9 OR n ≡ 8 mod 9, and
    n ≡ 1 mod 5 OR n ≡ 4 mod 5.

    We are guaranteed solutions from the CRT, since 16, 9, and 5 are coprime.

    So we have 2*2*2 = 8 general solutions modulo 720, and hence
    8 solutions under 720.

    I have a strong feeling I completely screwed this up. Any help?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by elemental View Post
    How many integers n are there such that 0 ≤ n ≤ 720 and n^2 ≡ 1 (mod 720)?

    I prime factorized 720 and did:
    n^2 ≡ 1 mod 16, and
    n^2 ≡ 1 mod 9, and
    n^2 ≡ 1 mod 5.
    (Since 16*9*5 = 720)

    Taking the modular square root, we observe that:
    n ≡ 1 mod 16 OR n ≡ 15 mod 16, and What about n ≡ 7 and n ≡ 9 (mod 16)?
    n ≡ 1 mod 9 OR n ≡ 8 mod 9, and
    n ≡ 1 mod 5 OR n ≡ 4 mod 5.

    We are guaranteed solutions from the CRT, since 16, 9, and 5 are coprime.

    So we have 2*2*2 = 8 general solutions modulo 720, and hence
    8 solutions under 720.
    Apart from that, everything looks good.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2010
    From
    NJ
    Posts
    68
    Ahh, thanks. 16 it is.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Given that -5≤x≤5 and -10≤y≤-2, find
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: October 2nd 2011, 05:12 AM
  2. Replies: 2
    Last Post: March 19th 2011, 01:38 AM
  3. Replies: 3
    Last Post: July 27th 2010, 03:46 PM
  4. Replies: 10
    Last Post: November 15th 2009, 06:04 PM
  5. Replies: 1
    Last Post: May 27th 2008, 07:56 AM

Search Tags


/mathhelpforum @mathhelpforum