Finding the GCD of Large Numbers Using Prime Factorization

Click For Summary
To find the GCD of 22,471 and 3,266, the Euclidean algorithm is recommended instead of prime factorization due to the large size of the numbers. This method involves repeated division to find the GCD efficiently. The user expresses familiarity with prime factorization for smaller numbers but seeks guidance on applying the Euclidean algorithm for larger values. The discussion emphasizes that prime factorization is not necessary for this problem. The solution can be expressed in the form 22,471x + 3,266y once the GCD is determined.
duki
Messages
264
Reaction score
0

Homework Statement



Find the gcd of 22,471 and 3,266 and express in the form 22,471x + 3,266y

Homework Equations



The Attempt at a Solution



I know how to get the gcd of easy numbers... using the prime factorization. But how do I do that with numbers of this scale?
 
Physics news on Phys.org


Use the Euclidean algorithm. You don't have to factorize them.
 


thank you!
 

Thread 'Distance between a Clock's hands when the distance is increasing most rapidly'

Question: A clock's minute hand has length 4 and its hour hand has length 3. What is the distance between the tips at the moment when it is increasing most rapidly?(Putnam Exam Question) Answer: Making assumption that both the hands moves at constant angular velocities, the answer is ## \sqrt{7} .## But don't you think this assumption is somewhat doubtful and wrong?
View full post »

Similar threads

Finding large prime factors (number theory)
  • · Replies 2 ·
Replies
2
Views
1K
Proving an integer is composite
  • · Replies 13 ·
Replies
13
Views
1K
Working Backwards from the GCD: Finding the Solution to a GCD Calculation
  • · Replies 5 ·
Replies
5
Views
2K
[Abstract Algebra] GCD and Relatively Prime Proof
  • · Replies 5 ·
Replies
5
Views
2K
Repeated Roots and Being Relatively Prime w/Derivative
  • · Replies 1 ·
Replies
1
Views
2K
Prime factors of odd composites
  • · Replies 6 ·
Replies
6
Views
2K
Finding GCD with Fibonacci: Base Case
  • · Replies 1 ·
Replies
1
Views
2K
Proving that lcm(a,b)gcd(a,b)=ab
  • · Replies 8 ·
Replies
8
Views
4K
Order of a^m when gcd(m,n) = 1
  • · Replies 2 ·
Replies
2
Views
2K
Proving gcd(a+b,ab) = 1 for Relatively Prime Numbers
  • · Replies 4 ·
Replies
4
Views
1K