Number Theory, with a proof discussed in class (not homework)

Click For Summary
SUMMARY

The discussion focuses on proving that the order of an element 'a' modulo 'm' (denoted as ordma) divides the order of 'a' modulo 'd' (denoted as ordda), under the conditions that d divides m (d|m) and the greatest common divisor of a and d is 1 (gcd(a,d)=1). The proof begins with the equation ax ≡ 1 (mod m) and transforms it using the relationship m = m'd, leading to the conclusion that ordma is indeed divisible by ordda. This establishes a fundamental property in number theory regarding the orders of elements in modular arithmetic.

PREREQUISITES
  • Understanding of modular arithmetic
  • Familiarity with the concept of order of an element in group theory
  • Knowledge of greatest common divisor (gcd) and its properties
  • Basic proof techniques in number theory
NEXT STEPS
  • Study the properties of orders in modular arithmetic
  • Learn about the implications of gcd in number theory
  • Explore advanced proof techniques in group theory
  • Investigate applications of number theory in cryptography
USEFUL FOR

Students of mathematics, particularly those studying number theory, as well as educators and anyone interested in the proofs and properties of modular arithmetic.

Worded.Mouse
Messages
2
Reaction score
0
Prove that ordda | ordma, when d|m.

Some conditions are 1 ≤ d, 1 ≤ m, and gcd(a,d)=1.

What I have so far:

let x=ordma, which gives us ax[itex]\equiv[/itex] 1 (mod m) [itex]\Rightarrow[/itex] ax=mk+1 for some k[itex]\in[/itex]Z

Let m=m'd. Then ax=mk+1=d(m'k)+1
 
Physics news on Phys.org
Could someone give me a hint?
 

Similar threads

Chinese Remainder theorem for 2 congruences
  • · Replies 2 ·
Replies
2
Views
2K
Can anyone please review/verify/check this number theory proof?
  • · Replies 12 ·
Replies
12
Views
2K
Can anyone please review/verify this proof of greatest common divisor?
  • · Replies 2 ·
Replies
2
Views
2K
Proving Inverses in Z/mZ* for Non-Prime Numbers
  • · Replies 6 ·
Replies
6
Views
2K
Prove that ##\lim\limits_{x \to \infty} f(x) = 0##
  • · Replies 3 ·
Replies
3
Views
2K
U(n) as an External Direct Product
  • · Replies 11 ·
Replies
11
Views
2K
Prove that the congruences admit a simultaneous solution
  • · Replies 5 ·
Replies
5
Views
2K
Proof of Monotone Classes and Subsets in Measure Theory
  • · Replies 2 ·
Replies
2
Views
2K
Can I Use Factor Sets to Solve GCD Problems?
  • · Replies 1 ·
Replies
1
Views
1K
Prove ##1 + a=s(a)=a+1## for ##a \in \mathbb{N}##
  • · Replies 1 ·
Replies
1
Views
2K