create account

[Math talk #26] Greatest Common Divisor by mathsolver

View this thread on: hive.blogpeakd.comecency.com
· @mathsolver ·
$0.28
[Math talk #26] Greatest Common Divisor
<center> <img src = "https://i.imgsafe.org/66/668fc101e8.jpeg"/></center>

([Image source Link](https://pixabay.com/en/pay-digit-number-fill-count-mass-1036469/), CC0 license)

# The Greatest common divisor
In the [last post](https://steemit.com/math/@mathsolver/math-talk-24-integer-division-algorithm) I introduced the integer division algorithm. Given two integers <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a,&space;b" title="a, b" align = "center"/> with <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b&space;\neq&space;0" title="b \neq 0" align = "center"/> , there exist unique quotient <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;q" title="q" align = "center"/> and remainder <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;r" title="r" /> such that 

- <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a&space;=&space;qb&space;&plus;&space;r" title="a = qb + r" align = "center"/> and 

- <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;0\leq&space;r&space;<&space;|b|" title="0\leq r < |b|" align = "center"/>

Of special significance is the case in which the remainder <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;r" title="r" /> turns out to be zero. (<img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;r=0" title="r=0" />)

## Divisors and multiples

We say an integer <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b" title="b" align = "center"/> is __divisible__ by <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="a" /> if there exist another integer <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;c" title="c" /> such that <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b&space;=&space;ac" title="b = ac" /> . Also <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="b" /> is said to be __divisor__ of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b" title="b" />. Conversely, <img src="http://latex.codecogs.com/gif.latex?\dpi{120}b" title="a \mid b" align = "center"/> is said to be __multiple__ of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="a" />. In mathematical notation, we write <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a&space;\mid&space;b" title="a \mid b" align ="center"/> . For negation, we use the symbol <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a\nmid b" title="\nmid" align = "center"/> to denote <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="a" /> is __not__ a divisor of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b" title="b" align = "center" /> . For example, 

1. <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;17&space;\mid&space;34" title="17 \mid 34" align = "center"/> because <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;34&space;=&space;17&space;\times&space;2" title="34 = 17 \times 2" align = "center"/>, but <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;20&space;\nmid&space;34" title="20 \nmid 34" align = "center"/> since <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;34&space;=&space;1&space;\times&space;20&space;&plus;&space;14" title="34 = 1 \times 20 + 14" align = "center"/> . 

2. Any integer <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="a" /> is a divisor of 0, since <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a&space;\times&space;0&space;=&space;0" title="a \times 0 = 0" /> is always true. 

3. Trivially, for any integer <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="a" />, <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\pm&space;1" title="\pm 1" align ="center"/> and <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\pm&space;a" title="\pm a" /> are divisors of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="a" />. So any non zero integer has at least 4 divisors, two of which are postive and two of which are negative. 

## Commmon divisors

Suppose we are given two integers   <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a,&space;b" title="a, b" align = "center"/> . For example, let's just put <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a&space;=&space;36,&space;b&space;=&space;20" title="a = 36, b = 20" align = "center"/> . A natural question would be 

<center><b><i> What are the common divisors? </i></b> </center>

Divisors of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;36" title="36" align = "center"/> are 

<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\pm1,&space;\pm2,&space;\pm3,&space;\pm4,&space;\pm6,&space;\pm9,&space;\pm&space;12,&space;\pm18,&space;\pm36" title="\pm1, \pm2, \pm3, \pm4, \pm6, \pm9, \pm 12, \pm18, \pm36" align = "center"/> </center>

and divisors of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;20" title="20" /> are 

<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\pm1,&space;\pm2,&space;\pm4,&space;\pm5,&space;\pm10,&space;\pm&space;20" title="\pm1, \pm2, \pm4, \pm5, \pm10, \pm 20" /> </center>

It is clear that <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\pm1,&space;\pm2,&space;\pm4" title="\pm1, \pm2, \pm4" align = "center"/> are common divisors. Exactly half of the common divisors are positive. Since negative divisors are nothing but negative sign attached to positive divisors, without loss of generality we can just consider about positive common divisors.

One more problem to resolve. If <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a=b=0" title="a=b=0" />, then since every integer serves as a common divisor of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a,&space;b" title="a, b" align  ="center"/>, the set of positive divisors is infinite set, <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\mathbb{N}" title="\mathbb{N}" align = "center"/>. So we must restrict our attention to pair of integers such that at least one is nonzero. Then, the set of positive common divisors of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a,&space;b" title="a, b" align = "center"/> is __finite set__. Finiteness guarantee the existence of __greatest common divisor__ of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="a" /> and <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b" title="b" /> . 

---
___Greatest common divisor.___ Let <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a,&space;b" title="a, b" align = "center"/> be given integers, with at least one of them different from zero. Then greatest common divisor of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="a" /> and <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b" title="b" />, denoted by <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\gcd(a,b)" title="\gcd(a,b)" align = "center"/> , is the positive integer <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;d" title="d" /> satisfying the following:

- <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;d&space;\mid&space;a" title="d \mid a" align = "center"/> and <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;d&space;\mid&space;b" title="d \mid b" align  ="center"/>

- If <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;c&space;\mid&space;a" title="c \mid a" align = "center"/> and <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;c&space;\mid&space;b" title="c \mid a" align = "center"/> , then <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;c&space;\leq&space;d" title="c \leq d" align = "center"/>

---

Following the above example, the greatest common divisor is, <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\gcd(36,&space;20)&space;=&space;4" title="\gcd(36, 20) = 4" align = "center"/> . 


## Properties of greatest common divisor

The most important property (or theorem) related with greatest common divisor is the following. 

---
___Linear Diophantine Equation.___ Given integers <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a,&space;b" title="a, b" align = "center"/>, not both of which are zero, there exist integers <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;x,&space;y" title="x, y" align = "center"/> such that 

<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\gcd(a,b)&space;=&space;ax&space;&plus;&space;by" title="\gcd(a,b) = ax + by" /> </center>

---

For example, again using <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a=36,&space;b=20" title="a=36, b=20" align = "center"/>, 

<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\gcd(36,20)&space;=&space;4&space;=&space;36&space;\times&space;(-1)&space;&plus;&space;20&space;\times&space;2" title="\gcd(36,20) = 4 = 36 \times (-1) + 20 \times 2" /> </center>

so appropriate integers are <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;x=-1,&space;y=2" title="x=-1, y=2" align = "center"/> . The existence, again, (if you read the previous post!) heavily relies on the well ordering principle. First, construct a collection of integers of the form <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;ax&space;&plus;&space;by" title="ax + by" align = "center"/>. 

<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;S&space;=&space;\left\{&space;ax&space;&plus;&space;by&space;:&space;x,&space;y&space;\text{&space;are&space;integers,&space;}&space;ax&space;&plus;&space;by&space;>&space;0\right\}" title="S = \left\{ ax + by : x, y \text{ are integers, } ax + by > 0\right\}" /> </center>

We must show that <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;S" title="S" /> is nonempty. Depending on the sign of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="a" />, we can put 

<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;x=1,&space;y=0" title="x=1, y=0" /> </center>

or 

<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;x=-1,&space;y=0" title="x=-1, y=0" /> </center>

For special case of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a=0" title="a=0" />, we can use either <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;x=0,&space;y=1" title="x=0, y=1" align = "center"/> or <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;x=0,&space;y=-1" title="x=0, y=1" align = 'center' />. So, <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;S" title="S" /> is clearly nonempty. Hence using the well ordering principle, there is a smallest element, namely <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;d" title="d" /> . Again by definition of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;S" title="S" /> , there is a pair of integers <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;(x_0,&space;y_0)" title="(x_0, y_0)" align = "center"/> such that 

<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;d&space;=&space;ax_0&space;&plus;&space;by_0" title="d = ax_0 + by_0" /> </center>

Now what's next? Well, we need to show that indeed <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;d&space;=&space;\gcd(a,b)" title="d = \gcd(a,b)" align ="center"/> ! This is straightforward. 

- If <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;d&space;\nmid&space;a" title="d \nmid a" align ="center"/> , then the division algorithm gives a relation 

<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a&space;=&space;qd&space;&plus;&space;r" title="a = qd + r" /> </center>

where <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;0&space;<&space;r&space;<&space;d" title="0 < r < d" />. However, 

<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;r&space;=&space;a&space;-&space;qd=a(1-qx_0)&plus;b(-qy_0)" title="r = a - qd=a(1-qx_0)+b(-qy_0)" /> </center>
so that <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;r&space;\in&space;S" title="r \in S" />. This contradicts to the fact that <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;d" title="d" /> is the smallest element. Thus <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;d&space;\mid&space;a" title="d \mid a" align = "center"/> . The same argument applies to <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b" title="b" />, so that <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;d&space;\mid&space;b" title="d \mid b" align = 'center'/> . 

- It is clear that the positive common divisors of a and b also divides <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;d" title="d" /> .

Summing up, <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;d" title="d" /> is greatest common divisor of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="a" /> and <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b" title="b" /> . 

Only problem to this proof is that it does not explicitly show how to find pair <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;x_0,&space;y_0" title="x_0, y_0" align = "center"/> . For example, if <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a,b" title="a,b" align = "center"/> are large integers; say <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a=1395,&space;b=4890" title="a=1395, b=4890" align ="center"/> how do we find the pairs? Well, the actual construction will be the topic of next post, Euclidean algorithm. 

## Relatively prime integers

We say two integers <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="a" /> and <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b" title="b" />, not both of which are zero, are said to be __relatively prime__ whenever <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\gcd(a,&space;b)&space;=&space;1" title="\gcd(a, b) = 1" align = "center"/> . Relatively prime integers are very special, because using linear diophantine theorem above, there is a pair of integers <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;x,y" title="x,y" align = "center"/> such that 

<center> <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;ax&space;&plus;&space;by=1" title="ax + by=1" /> </center>

Therefore, the set <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;S" title="S" /> is precisely, the set of positive integers, <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\mathbb{N}" title="\mathbb{N}" /> . 

## Conclusion

- <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;a" title="a" /> is a divisor of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b" title="b" /> if there exists another integer <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;c" title="c" /> such that <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;b=ac" title="b=ac" /> . 

- Positive and negative divisors are symmetric, so positive divisors are enough.  

- The solution to linear diophantine equation <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;ax&plus;by=c" title="ax+by=c"  align ="center"/> exists __if and only if__ <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;c" title="c" /> is a __multiple__ of <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\gcd(a,b)" title="\gcd(a,b)" align = "center"/> . 

- Relatively prime integers are the ones that <img src="http://latex.codecogs.com/gif.latex?\dpi{120}&space;\gcd&space;=&space;1" title="\gcd = 1" align = "center"/> . 

## Next?

The Euclidean algorithm and Water bucket problem . 

## Notable sources

- Elementary number theory 7th edition by David M.Burton, Section 2-3.
👍  , , , , , , , , , , , , , , , , , , ,
properties (23)
authormathsolver
permlinkmath-talk-26-greatest-common-divisor
categorymath
json_metadata"{"tags":["math","esteem","science","steemstem","steemiteducation"],"image":["https://i.imgsafe.org/66/668fc101e8.jpeg","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;a,&space;b","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;b&space;\\neq&space;0","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;q","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;r","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;a&space;=&space;qb&space;&plus;&space;r","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;0\\leq&space;r&space;<&space;|b|","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;r=0","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;b","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;a","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;c","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;b&space;=&space;ac","http://latex.codecogs.com/gif.latex?\\dpi{120}b","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;a&space;\\mid&space;b","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;a\\nmid b","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;17&space;\\mid&space;34","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;34&space;=&space;17&space;\\times&space;2","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;20&space;\\nmid&space;34","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;34&space;=&space;1&space;\\times&space;20&space;&plus;&space;14","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;a&space;\\times&space;0&space;=&space;0","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;\\pm&space;1","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;\\pm&space;a","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;a&space;=&space;36,&space;b&space;=&space;20","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;36","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;\\pm1,&space;\\pm2,&space;\\pm3,&space;\\pm4,&space;\\pm6,&space;\\pm9,&space;\\pm&space;12,&space;\\pm18,&space;\\pm36","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;20","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;\\pm1,&space;\\pm2,&space;\\pm4,&space;\\pm5,&space;\\pm10,&space;\\pm&space;20","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;\\pm1,&space;\\pm2,&space;\\pm4","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;a=b=0","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;\\mathbb{N}","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;\\gcd(a,b)","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;d","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;d&space;\\mid&space;a","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;d&space;\\mid&space;b","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;c&space;\\mid&space;a","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;c&space;\\mid&space;b","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;c&space;\\leq&space;d","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;\\gcd(36,&space;20)&space;=&space;4","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;x,&space;y","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;\\gcd(a,b)&space;=&space;ax&space;&plus;&space;by","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;a=36,&space;b=20","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;\\gcd(36,20)&space;=&space;4&space;=&space;36&space;\\times&space;(-1)&space;&plus;&space;20&space;\\times&space;2","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;x=-1,&space;y=2","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;ax&space;&plus;&space;by","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;S&space;=&space;\\left\\{&space;ax&space;&plus;&space;by&space;:&space;x,&space;y&space;\\text{&space;are&space;integers,&space;}&space;ax&space;&plus;&space;by&space;>&space;0\\right\\}","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;S","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;x=1,&space;y=0","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;x=-1,&space;y=0","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;a=0","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;x=0,&space;y=1","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;x=0,&space;y=-1","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;(x_0,&space;y_0)","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;d&space;=&space;ax_0&space;&plus;&space;by_0","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;d&space;=&space;\\gcd(a,b)","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;d&space;\\nmid&space;a","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;a&space;=&space;qd&space;&plus;&space;r","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;0&space;<&space;r&space;<&space;d","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;r&space;=&space;a&space;-&space;qd=a(1-qx_0)&plus;b(-qy_0)","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;r&space;\\in&space;S","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;x_0,&space;y_0","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;a,b","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;a=1395,&space;b=4890","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;\\gcd(a,&space;b)&space;=&space;1","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;x,y","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;ax&space;&plus;&space;by=1","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;b=ac","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;ax&plus;by=c","http://latex.codecogs.com/gif.latex?\\dpi{120}&space;\\gcd&space;=&space;1"],"links":["https://pixabay.com/en/pay-digit-number-fill-count-mass-1036469/","https://steemit.com/math/@mathsolver/math-talk-24-integer-division-algorithm"],"app":"steemit/0.1","format":"markdown"}"
created2018-09-10 12:59:18
last_update2018-09-10 12:59:18
depth0
children4
last_payout2018-09-17 19:56:51
cashout_time1969-12-31 23:59:59
total_payout_value0.234 HBD
curator_payout_value0.049 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length16,076
author_reputation1,337,981,311,807
root_title"[Math talk #26] Greatest Common Divisor"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd0
post_id70,881,022
net_rshares268,135,801,351
author_curate_reward""
vote details (20)
@amansharma555 ·
well post man, keep sharing...
properties (22)
authoramansharma555
permlinkre-mathsolver-math-talk-26-greatest-common-divisor-20180910t141335116z
categorymath
json_metadata{"tags":["math"],"app":"steemit/0.1"}
created2018-09-10 14:13:39
last_update2018-09-10 14:13:39
depth1
children0
last_payout2018-09-17 19:56:51
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length30
author_reputation273,717,128,923
root_title"[Math talk #26] Greatest Common Divisor"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id70,887,328
net_rshares0
@brokebook ·
Quite phenomenal number theory studied hundreds of years ago would lead to today's cryptography.
properties (22)
authorbrokebook
permlinkre-mathsolver-math-talk-26-greatest-common-divisor-20180910t193401342z
categorymath
json_metadata{"tags":["math"],"app":"steemit/0.1"}
created2018-09-10 19:34:03
last_update2018-09-10 19:34:03
depth1
children0
last_payout2018-09-17 19:56:51
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length96
author_reputation11,567,097,440
root_title"[Math talk #26] Greatest Common Divisor"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id70,912,406
net_rshares0
@pairplay1 ·
You received 0.43 % upvote as a reward From round 3 on 2018.09.10. Congrats!
properties (22)
authorpairplay1
permlinkre-mathsolver-math-talk-26-greatest-common-divisor-20180910t152445344z
categorymath
json_metadata""
created2018-09-10 15:24:48
last_update2018-09-10 15:24:48
depth1
children0
last_payout2018-09-17 19:56:51
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length76
author_reputation70,526,143
root_title"[Math talk #26] Greatest Common Divisor"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id70,893,844
net_rshares0
@steemitboard ·
Congratulations @mathsolver! You received a personal award!

<table><tr><td>https://steemitimages.com/70x70/http://steemitboard.com/@mathsolver/birthday1.png</td><td>Happy Birthday! - You are on the Steem blockchain for 1 year!</td></tr></table>

<sub>_You can view [your badges on your Steem Board](https://steemitboard.com/@mathsolver) and compare to others on the [Steem Ranking](https://steemitboard.com/ranking/index.php?name=mathsolver)_</sub>


> You can upvote this notification to help all Steem users. Learn how [here](https://steemit.com/steemitboard/@steemitboard/http-i-cubeupload-com-7ciqeo-png)!
properties (22)
authorsteemitboard
permlinksteemitboard-notify-mathsolver-20190814t063732000z
categorymath
json_metadata{"image":["https://steemitboard.com/img/notify.png"]}
created2019-08-14 06:37:33
last_update2019-08-14 06:37:33
depth1
children0
last_payout2019-08-21 06:37:33
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length610
author_reputation38,975,615,169,260
root_title"[Math talk #26] Greatest Common Divisor"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id89,505,291
net_rshares0