# Homework Help: Test Today Quick Number Theory Question

1. Feb 28, 2012

### trap101

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. Feb 28, 2012

### Ansatz7

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...

3. Feb 28, 2012

### trap101

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?

4. Feb 28, 2012

### Ansatz7

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.

5. Feb 28, 2012

### trap101

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

6. Feb 28, 2012

### Ansatz7

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!.

7. Feb 28, 2012

### trap101

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.