Can p be an odd prime that divides both r^2-s^2 and r^2+s^2?

Thread starter awesome220
Start date Nov 25, 2007
Tags

Theory

In summary, the GCD (Greatest Common Divisor) is the largest positive integer that divides evenly into two or more numbers. It is calculated using the Euclidean algorithm and is useful in number theory for simplifying fractions, finding the least common multiple, and determining whether two numbers are relatively prime. The GCD can be calculated for any number of integers using the iterative Euclidean algorithm. The GCD and LCM (Least Common Multiple) have a relationship described by the formula: GCD(a,b) * LCM(a,b) = a * b. The GCD of two numbers cannot be greater than both numbers, as it is always a factor of both and must be less than or equal to the smaller number.

Nov 25, 2007

awesome220

Can anyone help me with this?

If gcd(r,s)=1 then prove that gcd(r^2-s^2, r^2+s^2)=1 or 2.

i'm so confused.

Physics news on Phys.org

Nov 25, 2007

morphism

Science Advisor

Homework Helper

Let p be an odd prime that divides both r^2-s^2 and r^2+s^2. Show that this leads to a contradiction.

1. What is GCD and how is it calculated?

The GCD (Greatest Common Divisor) is the largest positive integer that divides evenly into two or more numbers. It is calculated using the Euclidean algorithm, which involves repeatedly dividing the larger number by the smaller number and using the remainder as the new divisor until the remainder is 0. The last non-zero remainder is the GCD.

2. How is GCD useful in number theory?

GCD is useful in number theory because it helps in simplifying fractions, finding the least common multiple, and determining whether two numbers are relatively prime. It also has applications in cryptography, prime factorization, and modular arithmetic.

3. Can the GCD of three or more numbers be calculated?

Yes, the GCD can be calculated for any number of integers. The process involves finding the GCD of the first two numbers, and then finding the GCD of that result with the third number, and so on until all numbers have been considered. This is known as the iterative Euclidean algorithm.

4. What is the relationship between GCD and LCM?

The GCD and LCM (Least Common Multiple) are two sides of the same coin. The GCD is the largest number that divides evenly into two or more numbers, while the LCM is the smallest number that is divisible by two or more numbers. Their relationship can be described by the formula: GCD(a,b) * LCM(a,b) = a * b.

5. Can the GCD of two numbers be greater than both numbers?

No, the GCD of two numbers cannot be greater than both numbers. The GCD is always a factor of both numbers, so it must be less than or equal to the smaller number. For example, the GCD of 12 and 18 is 6, which is a factor of both numbers and is less than both numbers.