Test Today Quick Number Theory Question

In summary, Test Today...Quick Number Theory Question asked a question about whether a2n (is congruent to) 1 (mod 2n+2), and the person provided a summary of what they did and what they were missing. They also provided a solution to a factorial and another question.
  • #1
trap101
342
0
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?
 
Physics news on Phys.org
  • #2


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


Nope. Test is 6pm my time, so I'm just tying up a few loose ends.
Ansatz7 said:
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?
 
  • #4


trap101 said:
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.
 
  • #5


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


trap101 said:
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!.
 
  • #7


Ansatz7 said:
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.
 

1. What is number theory?

Number theory is a branch of mathematics that studies the properties of numbers, including prime numbers, integers, and rational numbers.

2. How is number theory used in real life?

Number theory has practical applications in cryptography, computer science, and other fields. For example, the prime factorization of large numbers is used in cryptography to create secure codes.

3. What is a prime number?

A prime number is a positive integer that can only be divided by 1 and itself. Examples include 2, 3, 5, and 7.

4. How is number theory related to algebra and geometry?

Number theory is closely related to both algebra and geometry. It provides the foundation for many algebraic and geometric concepts, such as the fundamental theorem of arithmetic and Pythagorean theorem.

5. Can number theory be used to solve everyday problems?

Number theory can be applied to solve many everyday problems, such as finding the best deal when shopping or determining the probability of winning a lottery. It also helps develop critical thinking and problem-solving skills.

Similar threads

  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
792
  • Calculus and Beyond Homework Help
Replies
2
Views
780
  • Calculus and Beyond Homework Help
Replies
1
Views
5K
Replies
23
Views
1K
  • Calculus and Beyond Homework Help
Replies
16
Views
2K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
455
  • Calculus and Beyond Homework Help
Replies
20
Views
3K
Back
Top