Test Today Quick Number Theory Question

  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. 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. 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. 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. 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. 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. 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 a link to this question via email, Google+, Twitter, or Facebook

Have something to add?