Register to reply 
Test Today...Quick Number Theory Question 
Share this thread: 
#1
Feb2812, 10:15 AM

P: 339

Let "a" be an odd integer. Prove that a^{2n} (is congruent to) 1 (mod 2^{n+2})
Attempt: By using induction: Base Case of 1 worked. IH: Assume a^{2k} (is congruent to) 1 (mod 2^{k+2}) this can also be written: a^{2k} = 1 + (l) (2^{k+2}) for some "l" IS: a^{2k+1} = a^{2k°2} = (a^{2k)2} Now I took 1 + (l) (2^{k+2}) and substituted it into (a^{2k)2} and expanded: 1 + l ( 2^{k+3}+ (l) 2^{2k+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
Feb2812, 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(2^{k + 3}) + l^{2}(2^{2k + 4}) is congruent to 1 (mod 2^{k + 3}), which it is as far as I can tell...



#3
Feb2812, 12:56 PM

P: 339

Nope. Test is 6pm my time, so I'm just tying up a few loose ends.
How is : 1 + l(2^{k + 3}) + l^{2}(2^{2k + 4}) congruent to 1 (mod 2^{k + 3})? i tried breaking it up: 1 + l(2^{k + 3}) + l^{2}(2^{k + 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
Feb2812, 01:00 PM

P: 29

Test Today...Quick Number Theory Question



#5
Feb2812, 01:13 PM

P: 339

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) 15^{18} ≈ 1 (mod 19) (By Fermat's little) 17!(15)^{18} ≈ 1 (17!) (mod 19) => 17! ≈ 17! (mod 19) Also: 22 ≈ 3 (mod 19) => 22^{542} ≈ 3^{542} (mod 19) So altogether I have: (17!  3^{542})^{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
Feb2812, 01:18 PM

P: 29




#7
Feb2812, 01:35 PM

P: 339




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 