Test Today....Quick Number Theory Question


by trap101
Tags: number, test, theory, todayquick
trap101
trap101 is offline
#1
Feb28-12, 10:15 AM
P: 327
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 = a2k2 = (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?
Phys.Org News Partner Science news on Phys.org
Cougars' diverse diet helped them survive the Pleistocene mass extinction
Cyber risks can cause disruption on scale of 2008 crisis, study says
Mantis shrimp stronger than airplanes
Ansatz7
Ansatz7 is offline
#2
Feb28-12, 12:36 PM
P: 29
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...
trap101
trap101 is offline
#3
Feb28-12, 12:56 PM
P: 327
Nope. Test is 6pm my time, so I'm just tying up a few loose ends.


Quote Quote by Ansatz7 View Post
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...

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?

Ansatz7
Ansatz7 is offline
#4
Feb28-12, 01:00 PM
P: 29

Test Today....Quick Number Theory Question


Quote Quote by trap101 View Post
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?
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.
trap101
trap101 is offline
#5
Feb28-12, 01:13 PM
P: 327
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
Ansatz7
Ansatz7 is offline
#6
Feb28-12, 01:18 PM
P: 29
Quote Quote by trap101 View Post
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
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!.
trap101
trap101 is offline
#7
Feb28-12, 01:35 PM
P: 327
Quote Quote by Ansatz7 View Post
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)
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.


Register to reply

Related Discussions
a question from a test i had today Engineering, Comp Sci, & Technology Homework 2
Quick Question...Test at 8 am!! Introductory Physics Homework 2
test question today Introductory Physics Homework 9
question in my test today Calculus 5
Here's a question, today I had on my test Introductory Physics Homework 2