Extended Euclidean algorithm - Revision history

D.Lazard: /* Simplification of fractions */ fixing minus

2025-04-15T12:32:32Z

Simplification of fractions: fixing minus

← Previous revision		Revision as of 12:32, 15 April 2025
Line 192:		Line 192:
	'''if''' {{math\|1=''s'' = 0}} '''then output''' "Division by zero"		'''if''' {{math\|1=''s'' = 0}} '''then output''' "Division by zero"
	'''if''' {{math\|1=''s'' < 0}} '''then''' {{math\|1=''s'' := −''s''}}; {{math\|1=''t'' := −''t''}} (''for avoiding negative denominators'')		'''if''' {{math\|1=''s'' < 0}} '''then''' {{math\|1=''s'' := −''s''}}; {{math\|1=''t'' := −''t''}} (''for avoiding negative denominators'')
	'''if''' {{math\|1=''s'' = 1}} '''then output''' {{math\|-''t''}} (''for avoiding denominators equal to'' 1)		'''if''' {{math\|1=''s'' = 1}} '''then output''' {{math\|−''t''}} (''for avoiding denominators equal to'' 1)
	'''output''' {{math\|{{sfrac\|-''t''\|''s''}}}}		'''output''' {{math\|{{sfrac\|−''t''\|''s''}}}}

	The proof of this algorithm relies on the fact that {{math\|''s''}} and {{math\|''t''}} are two coprime integers such that {{math\|1=''as'' + ''bt'' = 0}}, and thus <math>\frac{a}{b} = -\frac{t}{s}</math>. To get the canonical simplified form, it suffices to move the minus sign for having a positive denominator.		The proof of this algorithm relies on the fact that {{math\|''s''}} and {{math\|''t''}} are two coprime integers such that {{math\|1=''as'' + ''bt'' = 0}}, and thus <math>\frac{a}{b} = -\frac{t}{s}</math>. To get the canonical simplified form, it suffices to move the minus sign for having a positive denominator.

D.Lazard: Reverted 1 edit by Cedar101 (talk): Uneplained change from math format to row html

2025-04-15T12:28:58Z

Reverted 1 edit by Cedar101 (talk): Uneplained change from math format to row html

← Previous revision		Revision as of 12:28, 15 April 2025
Line 190:		Line 190:
	==Simplification of fractions==		==Simplification of fractions==
	A fraction {{math\|{{sfrac\|''a''\|''b''}}}} is in canonical simplified form if {{math\|''a''}} and {{math\|''b''}} are [[coprime]] and {{math\|''b''}} is positive. This canonical simplified form can be obtained by replacing the three output lines of the preceding pseudo code by		A fraction {{math\|{{sfrac\|''a''\|''b''}}}} is in canonical simplified form if {{math\|''a''}} and {{math\|''b''}} are [[coprime]] and {{math\|''b''}} is positive. This canonical simplified form can be obtained by replacing the three output lines of the preceding pseudo code by
	'''if''' {{~~nowrap~~\|1=''s'' = 0}} '''then output''' "Division by zero"		'''if''' {{math\|1=''s'' = 0}} '''then output''' "Division by zero"
	'''if''' {{~~nowrap~~\|1=''s'' < 0}} '''then''' {{~~nowrap~~\|1=''s'' := −''s''}}; {{~~nowrap~~\|1=''t'' := −''t''}} (''for avoiding negative denominators'')		'''if''' {{math\|1=''s'' < 0}} '''then''' {{math\|1=''s'' := −''s''}}; {{math\|1=''t'' := −''t''}} (''for avoiding negative denominators'')
	'''if''' {{~~nowrap~~\|1=''s'' = 1}} '''then output''' {{~~nowrap~~\|−''t''}} (''for avoiding denominators equal to'' 1)		'''if''' {{math\|1=''s'' = 1}} '''then output''' {{math\|-''t''}} (''for avoiding denominators equal to'' 1)
	'''output''' {{sfrac\|-''t''\|''s''}}		'''output''' {{math\|{{sfrac\|-''t''\|''s''}}}}

	The proof of this algorithm relies on the fact that {{math\|''s''}} and {{math\|''t''}} are two coprime integers such that {{math\|1=''as'' + ''bt'' = 0}}, and thus <math>\frac{a}{b} = -\frac{t}{s}</math>. To get the canonical simplified form, it suffices to move the minus sign for having a positive denominator.		The proof of this algorithm relies on the fact that {{math\|''s''}} and {{math\|''t''}} are two coprime integers such that {{math\|1=''as'' + ''bt'' = 0}}, and thus <math>\frac{a}{b} = -\frac{t}{s}</math>. To get the canonical simplified form, it suffices to move the minus sign for having a positive denominator.

Cedar101: /* Simplification of fractions */ {{nowrap}}

2025-04-15T12:21:24Z

Simplification of fractions: {{nowrap}}

← Previous revision		Revision as of 12:21, 15 April 2025
Line 190:		Line 190:
	==Simplification of fractions==		==Simplification of fractions==
	A fraction {{math\|{{sfrac\|''a''\|''b''}}}} is in canonical simplified form if {{math\|''a''}} and {{math\|''b''}} are [[coprime]] and {{math\|''b''}} is positive. This canonical simplified form can be obtained by replacing the three output lines of the preceding pseudo code by		A fraction {{math\|{{sfrac\|''a''\|''b''}}}} is in canonical simplified form if {{math\|''a''}} and {{math\|''b''}} are [[coprime]] and {{math\|''b''}} is positive. This canonical simplified form can be obtained by replacing the three output lines of the preceding pseudo code by
	'''if''' {{~~math~~\|1=''s'' = 0}} '''then output''' "Division by zero"		'''if''' {{nowrap\|1=''s'' = 0}} '''then output''' "Division by zero"
	'''if''' {{~~math~~\|1=''s'' < 0}} '''then''' {{~~math~~\|1=''s'' := −''s''}}; {{~~math~~\|1=''t'' := −''t''}} (''for avoiding negative denominators'')		'''if''' {{nowrap\|1=''s'' < 0}} '''then''' {{nowrap\|1=''s'' := −''s''}}; {{nowrap\|1=''t'' := −''t''}} (''for avoiding negative denominators'')
	'''if''' {{~~math~~\|1=''s'' = 1}} '''then output''' {{~~math~~\|-''t''}} (''for avoiding denominators equal to'' 1)		'''if''' {{nowrap\|1=''s'' = 1}} '''then output''' {{nowrap\|−''t''}} (''for avoiding denominators equal to'' 1)
	'''output''' ~~{{math\|~~{{sfrac\|-''t''\|''s''}}}}		'''output''' {{sfrac\|-''t''\|''s''}}

	The proof of this algorithm relies on the fact that {{math\|''s''}} and {{math\|''t''}} are two coprime integers such that {{math\|1=''as'' + ''bt'' = 0}}, and thus <math>\frac{a}{b} = -\frac{t}{s}</math>. To get the canonical simplified form, it suffices to move the minus sign for having a positive denominator.		The proof of this algorithm relies on the fact that {{math\|''s''}} and {{math\|''t''}} are two coprime integers such that {{math\|1=''as'' + ''bt'' = 0}}, and thus <math>\frac{a}{b} = -\frac{t}{s}</math>. To get the canonical simplified form, it suffices to move the minus sign for having a positive denominator.

D.Lazard: Reverted 1 edit by 2806:2F0:5001:DF1A:1476:DE1D:999B:A8BA (talk): Unexplained change

2025-04-15T08:55:07Z

Reverted 1 edit by 2806:2F0:5001:DF1A:1476:DE1D:999B:A8BA (talk): Unexplained change

← Previous revision		Revision as of 08:55, 15 April 2025
Line 32:		Line 32:
	t_0 & =0 & t_1 & =1 \\		t_0 & =0 & t_1 & =1 \\
	& \,\,\,\vdots & & \,\,\,\vdots \\		& \,\,\,\vdots & & \,\,\,\vdots \\
	r_{i+1} & =r_{i-1}-~~q_{i+1}~~ r_i & \text {and } 0 & \le r_{i+1} < \|r_i\| & \text{(this defines } q_i \text{)}\\		r_{i+1} & =r_{i-1}-q_i r_i & \text {and } 0 & \le r_{i+1} < \|r_i\| & \text{(this defines } q_i \text{)}\\
	s_{i+1} & =s_{i-1}-~~q_{i+1}~~ s_i \\		s_{i+1} & =s_{i-1}-q_i s_i \\
	t_{i+1} & =t_{i-1}-~~q_{i+1}~~ t_i \\		t_{i+1} & =t_{i-1}-q_i t_i \\
	& \,\,\, \vdots		& \,\,\, \vdots
	\end{align}		\end{align}

2806:2F0:5001:DF1A:1476:DE1D:999B:A8BA: /* Description */

2025-04-15T00:55:01Z

Description

← Previous revision		Revision as of 00:55, 15 April 2025
Line 32:		Line 32:
	t_0 & =0 & t_1 & =1 \\		t_0 & =0 & t_1 & =1 \\
	& \,\,\,\vdots & & \,\,\,\vdots \\		& \,\,\,\vdots & & \,\,\,\vdots \\
	r_{i+1} & =r_{i-1}-~~q_i~~ r_i & \text {and } 0 & \le r_{i+1} < \|r_i\| & \text{(this defines } q_i \text{)}\\		r_{i+1} & =r_{i-1}-q_{i+1} r_i & \text {and } 0 & \le r_{i+1} < \|r_i\| & \text{(this defines } q_i \text{)}\\
	s_{i+1} & =s_{i-1}-~~q_i~~ s_i \\		s_{i+1} & =s_{i-1}-q_{i+1} s_i \\
	t_{i+1} & =t_{i-1}-~~q_i~~ t_i \\		t_{i+1} & =t_{i-1}-q_{i+1} t_i \\
	& \,\,\, \vdots		& \,\,\, \vdots
	\end{align}		\end{align}

MrGumballs: /* growthexperiments-addlink-summary-summary:2|1|0 */

2025-04-14T17:02:55Z

Link suggestions feature: 2 links added.

← Previous revision		Revision as of 17:02, 14 April 2025
Line 108:		Line 108:
	The matrix <math>A_1</math> is the identity matrix and its determinant is one. The determinant of the rightmost matrix in the preceding formula is −1. It follows that the determinant of <math>A_i</math> is <math>(-1)^{i-1}.</math> In particular, for <math>i=k+1,</math> we have <math>s_k t_{k+1} - t_k s_{k+1} = (-1)^k.</math> Viewing this as a Bézout's identity, this shows that <math>s_{k+1}</math> and <math>t_{k+1}</math> are [[coprime]]. The relation <math>as_{k+1}+bt_{k+1}=0</math> that has been proved above and [[Euclid's lemma]] show that <math>s_{k+1}</math> divides {{mvar\|b}}, that is that <math>b=ds_{k+1}</math> for some integer {{mvar\|d}}. Dividing by <math>s_{k+1}</math> the relation <math>as_{k+1}+bt_{k+1}=0</math> gives <math>a=-dt_{k+1}.</math> So, <math>s_{k+1}</math> and <math>-t_{k+1}</math> are coprime integers that are the quotients of {{mvar\|a}} and {{mvar\|b}} by a common factor, which is thus their greatest common divisor or its [[additive inverse\|opposite]].		The matrix <math>A_1</math> is the identity matrix and its determinant is one. The determinant of the rightmost matrix in the preceding formula is −1. It follows that the determinant of <math>A_i</math> is <math>(-1)^{i-1}.</math> In particular, for <math>i=k+1,</math> we have <math>s_k t_{k+1} - t_k s_{k+1} = (-1)^k.</math> Viewing this as a Bézout's identity, this shows that <math>s_{k+1}</math> and <math>t_{k+1}</math> are [[coprime]]. The relation <math>as_{k+1}+bt_{k+1}=0</math> that has been proved above and [[Euclid's lemma]] show that <math>s_{k+1}</math> divides {{mvar\|b}}, that is that <math>b=ds_{k+1}</math> for some integer {{mvar\|d}}. Dividing by <math>s_{k+1}</math> the relation <math>as_{k+1}+bt_{k+1}=0</math> gives <math>a=-dt_{k+1}.</math> So, <math>s_{k+1}</math> and <math>-t_{k+1}</math> are coprime integers that are the quotients of {{mvar\|a}} and {{mvar\|b}} by a common factor, which is thus their greatest common divisor or its [[additive inverse\|opposite]].

	To prove the last assertion, assume that ''a'' and ''b'' are both positive and <math>\gcd(a,b)\neq\min(a,b)</math>. Then, <math>a \neq b </math>, and if <math>a < b</math>, it can be seen that the ''s'' and ''t'' sequences for (''a'',''b'') under the EEA are, up to initial 0s and 1s, the ''t'' and ''s'' sequences for (''b'',''a''). The definitions then show that the (''a'',''b'') case reduces to the (''b'',''a'') case. So assume that <math>a > b</math> without loss of generality.		To prove the last assertion, assume that ''a'' and ''b'' are both positive and <math>\gcd(a,b)\neq\min(a,b)</math>. Then, <math>a \neq b </math>, and if <math>a < b</math>, it can be seen that the ''s'' and ''t'' sequences for (''a'',''b'') under the EEA are, up to initial 0s and 1s, the ''t'' and ''s'' sequences for (''b'',''a''). The definitions then show that the (''a'',''b'') case reduces to the (''b'',''a'') case. So assume that <math>a > b</math> [[without loss of generality]].

	It can be seen that <math>s_2</math> is 1 and <math>s_3</math> (which exists by <math>\gcd(a,b)\neq\min(a,b)</math>) is a negative integer. Thereafter, the <math>s_i</math> alternate in sign and strictly increase in magnitude, which follows inductively from the definitions and the fact that <math>q_i\geq 1</math> for <math>1 \leq i \leq k</math>, the case <math>i = 1</math> holds because <math>a > b</math>. The same is true for the <math>t_i</math> after the first few terms, for the same reason. Furthermore, it is easy to see that <math>q_k \geq 2</math> (when ''a'' and ''b'' are both positive and <math>\gcd(a,b)\neq\min(a,b)</math>). Thus, noticing that <math>\|s_{k+1}\| = \|s_{k-1}\| + q_k \|s_k\|</math>, we obtain		It can be seen that <math>s_2</math> is 1 and <math>s_3</math> (which exists by <math>\gcd(a,b)\neq\min(a,b)</math>) is a negative integer. Thereafter, the <math>s_i</math> alternate in sign and strictly increase in magnitude, which follows inductively from the definitions and the fact that <math>q_i\geq 1</math> for <math>1 \leq i \leq k</math>, the case <math>i = 1</math> holds because <math>a > b</math>. The same is true for the <math>t_i</math> after the first few terms, for the same reason. Furthermore, it is easy to see that <math>q_k \geq 2</math> (when ''a'' and ''b'' are both positive and <math>\gcd(a,b)\neq\min(a,b)</math>). Thus, noticing that <math>\|s_{k+1}\| = \|s_{k-1}\| + q_k \|s_k\|</math>, we obtain
Line 213:		Line 213:
	Thus {{math\|''t''}}, or, more exactly, the remainder of the division of {{math\|''t''}} by {{math\|''n''}}, is the multiplicative inverse of {{math\|''a''}} modulo {{math\|''n''}}.		Thus {{math\|''t''}}, or, more exactly, the remainder of the division of {{math\|''t''}} by {{math\|''n''}}, is the multiplicative inverse of {{math\|''a''}} modulo {{math\|''n''}}.

	To adapt the extended Euclidean algorithm to this problem, one should remark that the Bézout coefficient of {{math\|''n''}} is not needed, and thus does not need to be computed. Also, for getting a result which is positive and lower than ''n'', one may use the fact that the integer {{math\|''t''}} provided by the algorithm satisfies {{math\|{{!}}''t''{{!}} < ''n''}}. That is, if {{math\|''t'' < 0}}, one must add {{math\|''n''}} to it at the end. This results in the pseudocode, in which the input ''n'' is an integer larger than 1.		To adapt the extended Euclidean algorithm to this problem, one should remark that the Bézout coefficient of {{math\|''n''}} is not needed, and thus does not need to be computed. Also, for getting a result which is positive and lower than ''n'', one may use the fact that the integer {{math\|''t''}} provided by the algorithm satisfies {{math\|{{!}}''t''{{!}} < ''n''}}. That is, if {{math\|''t'' < 0}}, one must add {{math\|''n''}} to it at the end. This results in the [[pseudocode]], in which the input ''n'' is an integer larger than 1.
	'''function''' inverse(a, n)		'''function''' inverse(a, n)
	t := 0; newt := 1		t := 0; newt := 1

Atomvinter: /* Description */

2025-03-03T04:24:23Z

Description

← Previous revision		Revision as of 04:24, 3 March 2025
Line 50:		Line 50:
	This implies that the pair of Bézout's coefficients provided by the extended Euclidean algorithm is the ''minimal pair'' of Bézout coefficients, as being the unique pair satisfying both above inequalities.		This implies that the pair of Bézout's coefficients provided by the extended Euclidean algorithm is the ''minimal pair'' of Bézout coefficients, as being the unique pair satisfying both above inequalities.

	~~Also~~ it means that the algorithm can be done without [[integer overflow]] by a [[computer program]] using integers of a fixed size that is larger than that of ''a'' and ''b''.		It also means that the algorithm can be done without [[integer overflow]] by a [[computer program]] using integers of a fixed size that is larger than that of ''a'' and ''b''.

	=== Example ===		=== Example ===

MarkMarkB: Clarify "entries" to be "columns"

2024-11-03T21:35:44Z

Clarify "entries" to be "columns"

← Previous revision		Revision as of 21:35, 3 November 2024
Line 54:		Line 54:
	=== Example ===		=== Example ===

	The following table shows how the extended Euclidean algorithm proceeds with input {{nowrap\|{{green\|240}}}} and {{nowrap\|{{green\|46}}}}. The greatest common divisor is the last non zero entry, {{nowrap\|{{red\|2}}}} in the column "remainder". The computation stops at row 6, because the remainder in it is {{nowrap\|{{red\|0}}}}. Bézout coefficients appear in the last two ~~entries~~ of the second-to-last row. In fact, it is easy to verify that {{nowrap\|1={{magenta\|−9}} × {{green\|240}} + {{magenta\|47}} × {{green\|46}} = {{red\|2}}}}. Finally the last two entries {{nowrap\|{{cyan\|23}}}} and {{nowrap\|{{cyan\|−120}}}} of the last row are, up to the sign, the quotients of the input {{nowrap\|{{green\|46}}}} and {{nowrap\|{{green\|240}}}} by the greatest common divisor {{nowrap\|{{red\|2}}}}.		The following table shows how the extended Euclidean algorithm proceeds with input {{nowrap\|{{green\|240}}}} and {{nowrap\|{{green\|46}}}}. The greatest common divisor is the last non zero entry, {{nowrap\|{{red\|2}}}} in the column "remainder". The computation stops at row 6, because the remainder in it is {{nowrap\|{{red\|0}}}}. Bézout coefficients appear in the last two columns of the second-to-last row. In fact, it is easy to verify that {{nowrap\|1={{magenta\|−9}} × {{green\|240}} + {{magenta\|47}} × {{green\|46}} = {{red\|2}}}}. Finally the last two entries {{nowrap\|{{cyan\|23}}}} and {{nowrap\|{{cyan\|−120}}}} of the last row are, up to the sign, the quotients of the input {{nowrap\|{{green\|46}}}} and {{nowrap\|{{green\|240}}}} by the greatest common divisor {{nowrap\|{{red\|2}}}}.

	{\| class="wikitable" style="text-align:right;"		{\| class="wikitable" style="text-align:right;"

GünniX: Reflist

2024-10-12T04:22:20Z

Reflist

← Previous revision		Revision as of 04:22, 12 October 2024
Line 321:		Line 321:

	== References ==		== References ==
			{{Reflist}}
	* {{Cite book \|title=[[The Art of Computer Programming]] \|author-link=Donald Knuth \|first=Donald \|last=Knuth \|publisher=Addison-Wesley }} Volume 2, Chapter 4.		* {{Cite book \|title=[[The Art of Computer Programming]] \|author-link=Donald Knuth \|first=Donald \|last=Knuth \|publisher=Addison-Wesley }} Volume 2, Chapter 4.
	* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. {{ISBN\|0-262-03293-7}}. Pages 859–861 of section 31.2: Greatest common divisor.		* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. {{ISBN\|0-262-03293-7}}. Pages 859–861 of section 31.2: Greatest common divisor.

Anita5192: Reverted edit by 148.252.133.17 (talk) to last version by 96.36.47.50

2024-10-12T01:41:33Z

Reverted edit by 148.252.133.17 (talk) to last version by 96.36.47.50

← Previous revision		Revision as of 01:41, 12 October 2024
Line 137:		Line 137:
	where <math>\operatorname{Res}(a,b)</math> denotes the [[resultant]] of ''a'' and ''b''. In this form of Bézout's identity, there is no denominator in the formula. If one divides everything by the resultant one gets the classical Bézout's identity, with an explicit common denominator for the rational numbers that appear in it.		where <math>\operatorname{Res}(a,b)</math> denotes the [[resultant]] of ''a'' and ''b''. In this form of Bézout's identity, there is no denominator in the formula. If one divides everything by the resultant one gets the classical Bézout's identity, with an explicit common denominator for the rational numbers that appear in it.

	== Pseudocode==~~false positive~~		== Pseudocode==
	{{hatnote\|In this section and the following ones, '''''div''''' is an auxiliary function that computes the quotient of the [[Euclidean division]] of its left argument by its right argument.}}		{{hatnote\|In this section and the following ones, '''''div''''' is an auxiliary function that computes the quotient of the [[Euclidean division]] of its left argument by its right argument.}}
	To implement the algorithm that is described above, one should first remark that only the two last values of the indexed variables are needed at each step. Thus, for saving memory, each indexed variable must be replaced by just two variables.		To implement the algorithm that is described above, one should first remark that only the two last values of the indexed variables are needed at each step. Thus, for saving memory, each indexed variable must be replaced by just two variables.

← Previous revision		Revision as of 12:32, 15 April 2025
Line 192:		Line 192:
	'''if''' {{math\|1=''s'' = 0}} '''then output''' "Division by zero"		'''if''' {{math\|1=''s'' = 0}} '''then output''' "Division by zero"
	'''if''' {{math\|1=''s'' < 0}} '''then''' {{math\|1=''s'' := −''s''}}; {{math\|1=''t'' := −''t''}} (''for avoiding negative denominators'')		'''if''' {{math\|1=''s'' < 0}} '''then''' {{math\|1=''s'' := −''s''}}; {{math\|1=''t'' := −''t''}} (''for avoiding negative denominators'')
	'''if''' {{math\|1=''s'' = 1}} '''then output''' {{math\|-''t''}} (''for avoiding denominators equal to'' 1)		'''if''' {{math\|1=''s'' = 1}} '''then output''' {{math\|−''t''}} (''for avoiding denominators equal to'' 1)
	'''output''' {{math\|{{sfrac\|-''t''\|''s''}}}}		'''output''' {{math\|{{sfrac\|−''t''\|''s''}}}}

	The proof of this algorithm relies on the fact that {{math\|''s''}} and {{math\|''t''}} are two coprime integers such that {{math\|1=''as'' + ''bt'' = 0}}, and thus <math>\frac{a}{b} = -\frac{t}{s}</math>. To get the canonical simplified form, it suffices to move the minus sign for having a positive denominator.		The proof of this algorithm relies on the fact that {{math\|''s''}} and {{math\|''t''}} are two coprime integers such that {{math\|1=''as'' + ''bt'' = 0}}, and thus <math>\frac{a}{b} = -\frac{t}{s}</math>. To get the canonical simplified form, it suffices to move the minus sign for having a positive denominator.

← Previous revision		Revision as of 12:28, 15 April 2025
Line 190:		Line 190:
	==Simplification of fractions==		==Simplification of fractions==
	A fraction {{math\|{{sfrac\|''a''\|''b''}}}} is in canonical simplified form if {{math\|''a''}} and {{math\|''b''}} are [[coprime]] and {{math\|''b''}} is positive. This canonical simplified form can be obtained by replacing the three output lines of the preceding pseudo code by		A fraction {{math\|{{sfrac\|''a''\|''b''}}}} is in canonical simplified form if {{math\|''a''}} and {{math\|''b''}} are [[coprime]] and {{math\|''b''}} is positive. This canonical simplified form can be obtained by replacing the three output lines of the preceding pseudo code by
	'''if''' {{~~nowrap~~\|1=''s'' = 0}} '''then output''' "Division by zero"		'''if''' {{math\|1=''s'' = 0}} '''then output''' "Division by zero"
	'''if''' {{~~nowrap~~\|1=''s'' < 0}} '''then''' {{~~nowrap~~\|1=''s'' := −''s''}}; {{~~nowrap~~\|1=''t'' := −''t''}} (''for avoiding negative denominators'')		'''if''' {{math\|1=''s'' < 0}} '''then''' {{math\|1=''s'' := −''s''}}; {{math\|1=''t'' := −''t''}} (''for avoiding negative denominators'')
	'''if''' {{~~nowrap~~\|1=''s'' = 1}} '''then output''' {{~~nowrap~~\|−''t''}} (''for avoiding denominators equal to'' 1)		'''if''' {{math\|1=''s'' = 1}} '''then output''' {{math\|-''t''}} (''for avoiding denominators equal to'' 1)
	'''output''' {{sfrac\|-''t''\|''s''}}		'''output''' {{math\|{{sfrac\|-''t''\|''s''}}}}

	The proof of this algorithm relies on the fact that {{math\|''s''}} and {{math\|''t''}} are two coprime integers such that {{math\|1=''as'' + ''bt'' = 0}}, and thus <math>\frac{a}{b} = -\frac{t}{s}</math>. To get the canonical simplified form, it suffices to move the minus sign for having a positive denominator.		The proof of this algorithm relies on the fact that {{math\|''s''}} and {{math\|''t''}} are two coprime integers such that {{math\|1=''as'' + ''bt'' = 0}}, and thus <math>\frac{a}{b} = -\frac{t}{s}</math>. To get the canonical simplified form, it suffices to move the minus sign for having a positive denominator.

← Previous revision		Revision as of 12:21, 15 April 2025
Line 190:		Line 190:
	==Simplification of fractions==		==Simplification of fractions==
	A fraction {{math\|{{sfrac\|''a''\|''b''}}}} is in canonical simplified form if {{math\|''a''}} and {{math\|''b''}} are [[coprime]] and {{math\|''b''}} is positive. This canonical simplified form can be obtained by replacing the three output lines of the preceding pseudo code by		A fraction {{math\|{{sfrac\|''a''\|''b''}}}} is in canonical simplified form if {{math\|''a''}} and {{math\|''b''}} are [[coprime]] and {{math\|''b''}} is positive. This canonical simplified form can be obtained by replacing the three output lines of the preceding pseudo code by
	'''if''' {{~~math~~\|1=''s'' = 0}} '''then output''' "Division by zero"		'''if''' {{nowrap\|1=''s'' = 0}} '''then output''' "Division by zero"
	'''if''' {{~~math~~\|1=''s'' < 0}} '''then''' {{~~math~~\|1=''s'' := −''s''}}; {{~~math~~\|1=''t'' := −''t''}} (''for avoiding negative denominators'')		'''if''' {{nowrap\|1=''s'' < 0}} '''then''' {{nowrap\|1=''s'' := −''s''}}; {{nowrap\|1=''t'' := −''t''}} (''for avoiding negative denominators'')
	'''if''' {{~~math~~\|1=''s'' = 1}} '''then output''' {{~~math~~\|-''t''}} (''for avoiding denominators equal to'' 1)		'''if''' {{nowrap\|1=''s'' = 1}} '''then output''' {{nowrap\|−''t''}} (''for avoiding denominators equal to'' 1)
	'''output''' ~~{{math\|~~{{sfrac\|-''t''\|''s''}}}}		'''output''' {{sfrac\|-''t''\|''s''}}

	The proof of this algorithm relies on the fact that {{math\|''s''}} and {{math\|''t''}} are two coprime integers such that {{math\|1=''as'' + ''bt'' = 0}}, and thus <math>\frac{a}{b} = -\frac{t}{s}</math>. To get the canonical simplified form, it suffices to move the minus sign for having a positive denominator.		The proof of this algorithm relies on the fact that {{math\|''s''}} and {{math\|''t''}} are two coprime integers such that {{math\|1=''as'' + ''bt'' = 0}}, and thus <math>\frac{a}{b} = -\frac{t}{s}</math>. To get the canonical simplified form, it suffices to move the minus sign for having a positive denominator.