MHB Finding the Greatest Common Divisor of Two Integers

Thread starter matqkks
Start date Sep 13, 2018
Tags

Greatest common divisor Integers

Sep 13, 2018

matqkks

How do computers evaluate the gcd of two integers?

Mathematics news on Phys.org

Sep 13, 2018

castor28

Gold Member

MHB

matqkks said:

How do computers evaluate the gcd of two integers?

Hi,

They use Euclid's algorithm, described here. (Look in particular at section 2, Description).

Thread 'Trigonometry problem of interest'

Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...

View full post »

Thread 'Midpoint(s) of the unbounded number line'

Just chatting with my son about Maths and he casually mentioned that 0 would be the midpoint of the number line from -inf to +inf. I wondered whether it wouldn’t be more accurate to say there is no single midpoint. Couldn’t you make an argument that any real number is exactly halfway between -inf and +inf?

View full post »

Thread 'Arithmetic and our place value system'

A power has two parts. Base and Exponent. A number 423 in base 10 can be written in other bases as well: 1. 4* 10^2 + 2*10^1 + 3*10^0 = 423 2. 1*7^3 + 1*7^2 + 4*7^1 + 3*7^0 = 1143 3. 7*60^1 + 3*60^0 = 73 All three expressions are equal in quantity. But I have written the multiplier of powers to form numbers in different bases. Is this what place value system is in essence ?

View full post »

Feb 5, 2022

Replies: 2

Views: 1K

Can anyone please review/verify this proof of a nonzero integer a?

Feb 4, 2022

Replies: 5

Views: 2K

Can the GCD and Euclidean Algorithm Solve Real Life Problems?

Jul 9, 2013

Replies: 11

Views: 6K

MHB Greatest Common Divisor: Applications in Tiling and Number Theory

Jun 29, 2013

Replies: 1

Views: 2K

I How to evaluate the Greatest Common Divisor?

Jul 11, 2019

Replies: 2

Views: 1K

I Number of Integers (<N) divisible only by one power of 2

May 30, 2021

Replies: 6

Views: 1K

MHB Is $\gcd(n, n+2) = 1$ or $2$ for any integer $n$?

Jan 29, 2016

Replies: 5

Views: 2K

MHB Finding the Greatest EVEN Factor of X: Solving the GCD of m,n=2

Nov 10, 2015

Replies: 19

Views: 5K

Greatest common divisor of fractions and decimals

Jul 21, 2009

Replies: 2

Views: 13K

A The Last Occurrence of any Greatest Prime Factor

Jul 13, 2018

Replies: 7

Views: 1K

Bluesky LinkedIn

MHB Finding the Greatest Common Divisor of Two Integers

Thread 'Trigonometry problem of interest'

Thread 'Midpoint(s) of the unbounded number line'

Thread 'Arithmetic and our place value system'

Similar threads

Hot Threads

Insights Fermat's Last Theorem

B What could prove this wrong? I'm having a dispute with friends

B About a definition: What is the number of terms of a polynomial P(x)?

B Geometry Puzzle with 20 points in a cross pattern

I Geometry problem of interest with a 3-4-5 triangle

Recent Insights

Insights Thinking Outside The Box Versus Knowing What’s In The Box

Insights Why Entangled Photon-Polarization Qubits Violate Bell’s Inequality

Insights Quantum Entanglement is a Kinematic Fact, not a Dynamical Effect

Insights What Exactly is Dirac’s Delta Function? - Insight

Insights Relativator (Circular Slide-Rule): Simulated with Desmos - Insight

Insights Fixing Things Which Can Go Wrong With Complex Numbers