1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Test Today Quick Number Theory Question

  1. Feb 28, 2012 #1
    Test Today....Quick Number Theory Question

    Let "a" be an odd integer. Prove that a2n (is congruent to) 1 (mod 2n+2)

    Attempt: By using induction:
    Base Case of 1 worked.

    IH: Assume a2k (is congruent to) 1 (mod 2k+2)

    this can also be written: a2k = 1 + (l) (2k+2) for some "l"

    IS: a2k+1 = a2k°2 = (a2k)2

    Now I took 1 + (l) (2k+2) and substituted it into (a2k)2 and expanded:

    1 + l ( 2k+3+ (l) 22k+4) is what I obtained after expanding and then simplifying it. But I know this isn't what I have to obtain when I try and show the K+1 case. What am I missing?
     
  2. jcsd
  3. Feb 28, 2012 #2
    Re: Test Today....Quick Number Theory Question

    You've probably already had your test, but everything you have done so far is correct. Now you just need to show that 1 + l(2k + 3) + l2(22k + 4) is congruent to 1 (mod 2k + 3), which it is as far as I can tell...
     
  4. Feb 28, 2012 #3
    Re: Test Today....Quick Number Theory Question

    Nope. Test is 6pm my time, so I'm just tying up a few loose ends.



    How is : 1 + l(2k + 3) + l2(22k + 4) congruent to 1 (mod 2k + 3)?

    i tried breaking it up: 1 + l(2k + 3) + l2(2k + 2)2......so it's this last term that's giving me a problem. I also had one other short question if you don't mind?
     
  5. Feb 28, 2012 #4
    Re: Test Today....Quick Number Theory Question

    What is 22k+4 divided by 2k+3? Feel free to ask another question, though I can't guarantee that I'll be able to respond.
     
  6. Feb 28, 2012 #5
    Re: Test Today....Quick Number Theory Question

    The little things....smh.

    Well this one is easier I think:

    Find the remainder when (17!(15) - (22)542)2343 divided by 19

    Attempt: I started it like this: (let's just call this ≈ congruent for now (I don't know how to get it in this program)

    1518 ≈ 1 (mod 19) (By Fermat's little)

    17!(15)18 ≈ 1 (17!) (mod 19) => 17! ≈ 17! (mod 19)

    Also:

    22 ≈ 3 (mod 19) => 22542 ≈ 3542 (mod 19)

    So altogether I have: (17! - 3542)2343

    Now there is a factorial so I figure I'm going to have to use Wilson's Thm, but I can't see how to squeeze it in
     
  7. Feb 28, 2012 #6
    Re: Test Today....Quick Number Theory Question

    I wasn't familiar with Wilson's theorem (I last did number theory more than 2 years ago, and I haven't used it since) but from what I can see it tells you that 18! is congruent to -1 mod 19. 18! = 18 * 17!, so I believe you can use this to simplify 17!.
     
  8. Feb 28, 2012 #7
    Re: Test Today....Quick Number Theory Question

    and here I was thinking that I might have some grandiose use for this in the future, maybe I'll figure some use for it. Thanks though, you've been a help.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Similar Discussions: Test Today Quick Number Theory Question
Loading...