Proof of the Order Divisibility Property

In summary, the Order Divisibility Property states that if an = 1 (mod p), then the order ep(a) of a (mod p) divides n. To prove this, one can use the division algorithm to show that r must equal zero. Additionally, if a is relatively prime to p, the congruence am = an (mod p) holds when e_p(a) = p-1. To prove this, one must consider the definition of 'order' and manipulate it to fit the given premises. The division algorithm can also be used to show that the order must be less than p-1.
  • #1
squire636
39
0
The Order Divisibility Property states that if an = 1 (mod p), then the order ep(a) of a (mod p) divides n.

How can I go about proving this?

Additionally, if a is relatively prime to p, when does the congruence am = an (mod p) hold? Is there a proof for this as well?

Thanks!
 
Physics news on Phys.org
  • #2
Hint for 1: The division algorithm says we can write ##n=qe_p(a)+r##. What can you say about r?

Hint for 2: If a is relatively prime to p, what is ##e_p(a)##?
 
  • #3
For the first one, r must equal zero, but I'm not sure how to show that it is true.

For the second, would the order ep(a) = p-1 ?
 
  • #4
squire636 said:
For the second, would the order ep(a) = p-1 ?

Not really; other integer less than p-1 could do the trick. Anyway, I believe morphism was simply trying to make you think about the very definition of 'order'. And what would you need to do to this definition in order to transform it into something like the premises that you are given.
 
  • #5
As for the first problem, the division algorithm tells us that ##0 \leq r < e_p(a)##. What can you do with this, squire636?
 

1. What is the Order Divisibility Property?

The Order Divisibility Property is a mathematical concept that states that if a number, n, divides another number, m, then n must also divide any multiple of m. In other words, if m is divisible by n, then any multiple of m will also be divisible by n.

2. How does the Order Divisibility Property work?

The Order Divisibility Property works by using the concept of division. If a number, n, is a divisor of another number, m, then m can be written as n multiplied by some other number, k. This means that any multiple of m can also be written as n multiplied by the same value of k, which shows that n is also a divisor of the multiple of m.

3. Why is the Order Divisibility Property important?

The Order Divisibility Property is important because it allows us to make conclusions about the divisibility of numbers without having to perform calculations. By understanding this property, we can quickly determine if a number is a divisor of another number, which can be useful in many mathematical and scientific applications.

4. How is the Order Divisibility Property used in real life?

The Order Divisibility Property is used in many real-life scenarios, such as in finance and coding. For example, in finance, understanding this property can help with calculating interest rates and determining the profitability of investments. In coding, it can be used to optimize algorithms and improve efficiency in computer programs.

5. Are there any exceptions to the Order Divisibility Property?

Yes, there are a few exceptions to the Order Divisibility Property. One exception is when the divisor, n, is equal to 1. In this case, any multiple of m will also be divisible by 1, regardless of what m is. Another exception is when the divisor, n, is equal to 0. In this case, the property does not hold, as any number divided by 0 is undefined. Additionally, when dealing with irrational numbers or complex numbers, the property may not apply.

Similar threads

  • Linear and Abstract Algebra
Replies
17
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
704
  • Precalculus Mathematics Homework Help
Replies
17
Views
2K
  • Linear and Abstract Algebra
Replies
1
Views
919
  • Linear and Abstract Algebra
Replies
3
Views
963
  • Linear and Abstract Algebra
Replies
1
Views
622
  • Linear and Abstract Algebra
Replies
11
Views
1K
  • Precalculus Mathematics Homework Help
Replies
32
Views
1K
  • Linear and Abstract Algebra
Replies
8
Views
854
  • Linear and Abstract Algebra
Replies
1
Views
862
Back
Top