Prove Congruence: Prime p|/a & Additive Order of a Modulo p = p

  • Thread starter kathrynag
  • Start date
  • Tags
    Proof
In summary, if p is a prime number and a is any integer with p|/a, then the additive order of a modulo p is equal to p. This is because p must be the smallest positive solution to ax ≡ 0 mod p, since p does not divide a. This is a defining property of prime numbers, as p must either divide x or 1. Therefore, p must divide x, and the additive order of a modulo p is p.
  • #1
kathrynag
598
0

Homework Statement


prove that if p is a prime number and a is any integer p|/a(p does not divide a), then the additive order of a modulo p is equal to p.


Homework Equations





The Attempt at a Solution


I know p|/ a says a[tex]\neq[/tex]pn for an integer n.
The additive order of a modulo n is the smallest positive solution to ax[tex]\equiv[/tex]0 mod n.
Let p be a prime number and p|/ a.
Then we can say (p, a)=1. That is p and a are relatively prime.
That's as far as I got.
 
Physics news on Phys.org
  • #2
ax=0 mod p means that p|ax. If p does not divide a, what can you infer?
 
  • #3
the additive order is p?
 
  • #4
Why?
 
  • #5
Since p does not divide a, there are no multiples of a that equal p. Thus, p must be the smallest additive order.
 
  • #6
kathrynag said:
Since p does not divide a, there are no multiples of a that equal p. Thus, p must be the smallest additive order.

p not dividing a means no multiple of p equals a, not that no multiple of a equals p. And I don't see what that has to do with additive order anyway... 4 does not divide six, there are no multiples of 4 or 6 that give the other one, but the additive order of 4 mod 6 is three, not six.

If p|ax and p does not divide a, and p is a prime, what must p divide? This is the defining property of prime numbers
 
  • #7
p divides x or p divides 1
 
  • #8
p can't divide 1...

You should be able to finish the proof now
 
  • #9
Ok I think this makes a bit more sense for em now. Thanks!
 

1. What is the significance of proving congruence in relation to prime numbers and additive order modulo p?

Proving congruence between two numbers, a and b, means that they have the same remainder when divided by a certain number, p. This is significant when p is a prime number because it allows us to understand the relationship between a and b in terms of their divisibility by p. Additionally, the additive order of a modulo p represents the smallest positive integer k such that a^k is congruent to 1 mod p. This can provide valuable insights into the properties of a and its relationship to p.

2. How can we prove congruence between two numbers when one is a prime factor of the other?

If p is a prime factor of a, then a = kp for some integer k. To prove that a is congruent to 0 mod p, we simply need to show that a divided by p leaves a remainder of 0. This can be done using long division or by using the definition of congruence, which states that a is congruent to b mod p if and only if p divides (a-b).

3. Why is the additive order of a modulo p important in this context?

The additive order of a modulo p is important because it tells us how many times we can add a modulo p to itself before we reach a number that is congruent to 1 mod p. This can provide valuable information about the structure of a and its relationship to p. Additionally, the additive order can help us determine if a is a primitive root modulo p, which has implications in number theory and cryptography.

4. Can we use modular arithmetic to prove congruence for non-prime numbers?

Yes, we can use modular arithmetic to prove congruence for any two numbers, regardless of whether they are prime or not. The definition of congruence states that a is congruent to b mod p if and only if p divides (a-b). This means that we can use modular arithmetic to show that two numbers have the same remainder when divided by a certain number, regardless of whether that number is prime or not.

5. Are there any practical applications of proving congruence and the additive order of a modulo p?

Yes, there are many practical applications of proving congruence and the additive order of a modulo p. For example, in cryptography, the additive order can be used to generate large prime numbers for secure encryption. It can also be used to determine the primitive roots of a prime number, which are important in certain encryption algorithms. Additionally, congruence and the additive order have applications in number theory, abstract algebra, and computer science.

Similar threads

Congruence and Primes: Proving the Order of an Integer Modulo a Prime
    • Calculus and Beyond Homework Help
Replies
4
Views
950
If ## p\neq5 ## is an odd prime, prove that either ## p^{2}-1 ## or....
    • Calculus and Beyond Homework Help
Replies
15
Views
2K
Prove that if p > 3 is a prime number, then p^2 = [....]
    • Calculus and Beyond Homework Help
Replies
16
Views
2K
Proving an integer problem about the sum of a square number and a prime number
    • Calculus and Beyond Homework Help
Replies
18
Views
2K
Proving Primitive Roots of Odd Numbers Modulo pm
    • Calculus and Beyond Homework Help
Replies
3
Views
1K
Strong Induction: Proving Every Int n>1 is a Product of Primes
    • Calculus and Beyond Homework Help
Replies
5
Views
1K
Prime factors of odd composites
    • Calculus and Beyond Homework Help
Replies
6
Views
1K
Proving Closure and Identity for U(n)
    • Calculus and Beyond Homework Help
Replies
16
Views
4K
Proof: There Exists a prime p such that p=< sqrt(n)
    • Calculus and Beyond Homework Help
Replies
6
Views
2K
Proofs By Induction: Proving P(n) for All n
    • Calculus and Beyond Homework Help
Replies
3
Views
1K

Hot Threads

Recent Insights

Back
Top