Test Today....Quick Number Theory Question

trap101

Let "a" be an odd integer. Prove that a²ⁿ (is congruent to) 1 (mod 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?

Ansatz7

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^{2k + 4}) is congruent to 1 (mod 2^{k + 3}), which it is as far as I can tell...

trap101

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^{2k + 4}) congruent to 1 (mod 2^{k + 3})?

i tried breaking it up: 1 + l(2^{k + 3}) + l²(2^{k + 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

What is 2^2k+4 divided by 2^k+3? Feel free to ask another question, though I can't guarantee that I'll be able to respond.

trap101

The little things....smh.

Well this one is easier I think:

Find the remainder when (17!(15) - (22)⁵⁴²)²³⁴³ 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¹⁸ ≈ 1 (mod 19) (By Fermat's little)

17!(15)¹⁸ ≈ 1 (17!) (mod 19) => 17! ≈ 17! (mod 19)

Also:

22 ≈ 3 (mod 19) => 22⁵⁴² ≈ 3⁵⁴² (mod 19)

So altogether I have: (17! - 3⁵⁴²)²³⁴³

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

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

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.