Solving $(a,b)=1 \Rightarrow (a^m,b^n)=1$ without Primes

  • MHB
  • Thread starter evinda
  • Start date
In summary, the conversation is about proving that if the greatest common divisor of two numbers is 1, then the greatest common divisor of their respective powers is also 1. One person suggests using Bézout's identity and expanding a linear combination of the numbers, while the other wonders if they need to show that the greatest common divisors of the numbers and their respective powers are also 1.
  • #1
evinda
Gold Member
MHB
3,836
0
Hey! :)

I have to show that if $(a,b)=1 \Rightarrow (a^m,b^n)=1$,without using primes!
Suppose that $d=(a^m,b^n)$.Then $d|a^m , d|b^n$.
How can I continue?
Do I have to show that $(a^{m-1},d)=1$ and $(b^{n-1},d)=1$? If yes,how could I do this? :confused:
 
Mathematics news on Phys.org
  • #2
evinda said:
Hey! :)

I have to show that if $(a,b)=1 \Rightarrow (a^m,b^n)=1$,without using primes!
Suppose that $d=(a^m,b^n)$.Then $d|a^m , d|b^n$.
How can I continue?
Do I have to show that $(a^{m-1},d)=1$ and $(b^{n-1},d)=1$? If yes,how could I do this? :confused:

Hi!

I have a different approach.

From $(a,b)=1$ we know that there are numbers x and y such that $ax+by=1$ (Bézout's identity).

Now expand $(ax+by)^{m+n}$ and write it as a linear combination of $a^m$ and $b^n$...
 

FAQ: Solving $(a,b)=1 \Rightarrow (a^m,b^n)=1$ without Primes

1. How can I prove that if $(a,b)=1$, then $(a^m,b^n)=1$ without using primes?

One way to prove this is by using the fundamental theorem of arithmetic, which states that every positive integer can be uniquely expressed as a product of primes. By showing that the prime factorization of $a^m$ and $b^n$ have no common factors, we can conclude that $(a^m,b^n)=1$.

2. Can this theorem be extended to non-positive integers?

No, this theorem only applies to positive integers. In fact, for negative integers, the statement is not always true. For example, if we take $a=-2$ and $b=3$, we have $(a,b)=1$ but $(a^2,b^3)=6$.

3. Are there any other methods to prove this theorem without using primes?

Yes, there are other methods such as using the Euclidean algorithm or the Bezout's identity. The Euclidean algorithm involves finding the greatest common divisor of two numbers, while Bezout's identity states that for any two integers $a$ and $b$, there exist integers $x$ and $y$ such that $ax+by=(a,b)$. Both of these methods can be used to prove the theorem without using primes.

4. Is this theorem only applicable to integers?

Yes, this theorem only applies to integers. It does not hold true for other types of numbers such as fractions, decimals, or irrationals.

5. How is this theorem useful in mathematics?

This theorem is useful in many areas of mathematics, such as number theory, algebra, and cryptography. It allows us to determine if two numbers are relatively prime without using primes, which can be helpful in simplifying equations and solving problems involving integers. Additionally, this theorem has applications in cryptography, as it can be used to ensure that two numbers are coprime, which is important for the security of many encryption algorithms.

Similar threads

I How Does the Equation D x E mod Φ(N) = 1 Relate to RSA Encryption?
Replies
1
Views
1K
I Are there any two pairs of integers with the same result in a specific function?
Replies
7
Views
1K
A Are these two optimization problems equivalent?
Replies
1
Views
1K
MHB Show Equivalence: $a^d \equiv 1 \pmod n$
Replies
3
Views
2K
I Evaluation of the sum 1^m+3^m+5^m+ ....................(2n+1)^{m}
Replies
1
Views
301
MHB Proving or disproving this matrix V is invertible.
Replies
1
Views
946
MHB For which n is the term an integer & Calculate the equivalence
Replies
4
Views
1K
B Looking for context for a textbook quote
Replies
9
Views
1K
I Arithmetic representation of symbols according to certain rules
2
Replies
35
Views
3K
MHB Calculating RSA Signature at Message m=2 w/o Hash Function
Replies
3
Views
2K

Hot Threads

Recent Insights

Back
Top