Deprecated: Methods with the same name as their class will not be constructors in a future version of PHP; plgContentJComments has a deprecated constructor in /var/www/astarmathsandphysics/plugins/content/jcomments/jcomments.php on line 25 Call Stack: 0.0001 362456 1. {main}() /var/www/astarmathsandphysics/index.php:0 0.0545 1211848 2. Joomla\CMS\Application\SiteApplication->execute() /var/www/astarmathsandphysics/index.php:49 0.0545 1211848 3. Joomla\CMS\Application\SiteApplication->doExecute() /var/www/astarmathsandphysics/libraries/src/Application/CMSApplication.php:267 0.1339 4127384 4. Joomla\CMS\Application\SiteApplication->dispatch() /var/www/astarmathsandphysics/libraries/src/Application/SiteApplication.php:233 0.1352 4155016 5. Joomla\CMS\Component\ComponentHelper::renderComponent() /var/www/astarmathsandphysics/libraries/src/Application/SiteApplication.php:194 0.1360 4172728 6. Joomla\CMS\Component\ComponentHelper::executeComponent() /var/www/astarmathsandphysics/libraries/src/Component/ComponentHelper.php:356 0.1362 4203248 7. require_once('/var/www/astarmathsandphysics/components/com_content/content.php') /var/www/astarmathsandphysics/libraries/src/Component/ComponentHelper.php:381 0.1372 4225968 8. ContentController->execute() /var/www/astarmathsandphysics/components/com_content/content.php:42 0.1372 4225968 9. ContentController->display() /var/www/astarmathsandphysics/libraries/src/MVC/Controller/BaseController.php:710 0.1961 4928136 10. ContentController->display() /var/www/astarmathsandphysics/components/com_content/controller.php:113 0.1997 5120288 11. Joomla\CMS\Cache\Controller\ViewController->get() /var/www/astarmathsandphysics/libraries/src/MVC/Controller/BaseController.php:663 0.2002 5141216 12. ContentViewArticle->display() /var/www/astarmathsandphysics/libraries/src/Cache/Controller/ViewController.php:102 0.2111 5350488 13. Joomla\CMS\Plugin\PluginHelper::importPlugin() /var/www/astarmathsandphysics/components/com_content/views/article/view.html.php:189 0.2111 5350744 14. Joomla\CMS\Plugin\PluginHelper::import() /var/www/astarmathsandphysics/libraries/src/Plugin/PluginHelper.php:182

The Euclidean Algorithm

The greatest common divisor of two numbersandmay be found from the prime – power factorizations ofandare known. Considerable computing power may be needed to find the prime power factorizations however and there is a procedure – Euclid's algorithm - that requires less computation.

We need the following theorem

Theorem 1 The Division Algorithm

Given two numbersandwiththere exists a unique pair of integerscalled the quotient andcalled the remainder such thatwithMoreover,if and only ifdivides

Proof: Letbe the set of nonnegative integers given by This is a nonempty set of nonnegative integers so it has a smallest member, sayLetthen andNow we show thatAssumethenbut sincehenceis a member ofsmaller than it's smallest member,This contradiction shows thatThe pairis unique for if there were another such pair, saythen sohencedividesIfthen a contradiction thereforeandFinallyif and only ifdivides

The above theorem gives us a method for finding q and r. We subtract from or add to a enough multiples of b until we have found the sammlest nonnegative number of the form a-bx.

Theorem 2 The Euclidean Algorithm

Given positive integers a and b wherelet r-0 =a and r-1 =b and apply the division algorithm repeatedly to obtain a set of remainders r-2 , r-3 , ..., r-n , r-{n+1} defined recursively by the relations

Thenthe last nonzero remainder in this process, isthe greatest common divisor of a and b.

Proof: There is a stage at whichbecause theare decreasing and nonnegative. The last relationshows thatdividesThe next to last shows thatdivides so by inductiondivides eachIn particularandsois a common divisor ofandLetbe any common divisor ofandThe definition ofshows that dividesthen the line below shows thatdividesso by inductiondivides eachso divideshence

Example: Find the greatest common divisor of 19 and 7.




The greatest common divisor of 19 and 7 is thus 1.

We can use the Euclidean algorithm to write the greatest common divisor of two numbersandas a linear combination ofand

For the example aboveandwe have from (3)


Rearrange (2) to giveand substitute into (4)


Rearrange (1) to giveand substitute into (5)

which rearranges to give