<Text-field layout="_pstyle4" style="_pstyle4">The division algorithm</Text-field>

Divisibility

modp(20,7);

NiMiIic=

modp(23312, 232);

NiMiJDci

(23312-112)/232;

NiMiJCsi

<Text-field layout="_pstyle4" style="_pstyle4">Greatest common divisor</Text-field>

gcd(81959,73963);

NiMiJSoqPg==

ourlcm := (a,b) -> a*b / gcd(a,b): ourlcm(18,24);

NiMiI3M=

<Text-field layout="_pstyle4" style="_pstyle4">The Euclidean algorithm</Text-field>

ourgcd := proc(a,b) local atemp, btemp; (atemp, btemp) := (a, b); while btemp > 0 do (atemp, btemp) := (btemp,modp(atemp,btemp)); end do; atemp; end proc: ourgcd(81959,73963);

NiMiJSoqPg==

ourgcdcount := proc(a,b) local atemp, btemp, c; (atemp, btemp) := (a, b); c := 0; while btemp > 0 do (atemp, btemp) := (btemp, modp(atemp,btemp)); c := c+1; end do; [atemp, c]; end proc:

ourgcdcount(81959,73963);

NiM3JCIlKio+IiIk

ourgcdcount(12413141414234242423413412,123123123909023233211);

NiM3JCIiIiIjUA==

ourgcdcount(987,610);

NiM3JCIiIiIjOQ==

<Text-field layout="_pstyle4" style="_pstyle4">Linear Combinations</Text-field>

ourextendedgcd := proc(a,b) local atemp, btemp, x, xx, y, yy, r, q; (atemp, btemp) := (a, b); (xx, x) := (1, 0); (yy, y) := (0, 1); while btemp > 0 do r := modp(atemp,btemp); q := (atemp-r)/btemp; (atemp, btemp) := (btemp, r); (xx, x) := (x, xx - x*q); (yy, y) := (y, yy - y*q); end do; [atemp, (xx,yy)]; end proc: ourextendedgcd(817,615);

NiM3JSIiIiEkUCIiJCM9

<Text-field layout="_pstyle4" style="_pstyle4">Primes</Text-field>

ithprime(5);

NiMiIzY=

[seq(ithprime(n),n = 1 .. 100)];

NiM3YHEiIiMiIiQiIiYiIigiIzYiIzgiIzwiIz4iI0IiI0giI0oiI1AiI1QiI1YiI1oiI2AiI2YiI2giI24iI3IiI3QiI3oiIyQpIiMqKSIjKCoiJCwiIiQuIiIkMiIiJDQiIiQ4IiIkRiIiJEoiIiRQIiIkUiIiJFwiIiReIiIkZCIiJGoiIiRuIiIkdCIiJHoiIiQiPSIkIj4iJCQ+IiQoPiIkKj4iJDYjIiRCIyIkRiMiJEgjIiRMIyIkUiMiJFQjIiReIyIkZCMiJGojIiRwIyIkciMiJHgjIiQiRyIkJEciJCRIIiQyJCIkNiQiJDgkIiQ8JCIkSiQiJFAkIiRaJCIkXCQiJGAkIiRmJCIkbiQiJHQkIiR6JCIkJFEiJCpRIiQoUiIkLCUiJDQlIiQ+JSIkQCUiJEolIiRMJSIkUiUiJFYlIiRcJSIkZCUiJGglIiRqJSIkbiUiJHolIiQoWyIkIlwiJCpcIiQuJiIkNCYiJEAmIiRCJiIkVCY=

ifactor(14151353);

NiMqJi0lIUc2IyIjUCIiIy1GJTYjIiZQLiIiIiI=

numtheory[pi](1000000);

NiMiJilceQ==

array(map(x->[x,numtheory[pi](x),evalf(x/ln(x)),evalf(numtheory[pi](x)/(x/ln(x)))],[seq(10^i,i=1..7)]));

NiMtJSdtYXRyaXhHNiM3KTcmIiM1IiIlJCIrPlslSE0lISIqJCIrcy5NNSMqISM1NyYiJCsiIiNEJCIrNUNackAhIikkIitZREheNkYsNyYiJSs1IiRvIiQiK3QjW3dXIiEiKCQiKygpR11nNkYsNyYiJisrIiIlSDckIiswaXQmMyIhIickIitLMyY+OCJGLDcmIicrKzUiJSNmKiQiK1EnKillbylGRSQiKzYpPlY1IkYsNyYiKCsrKyIiJilceSQiK204Q1FzISImJCIrWyoqWyUzIkYsNyYiKSsrKzUiJ3pYbSQiKycpbz8vaSEiJSQiKyp5dTYyIkYs

<Text-field layout="Heading 1" style="Heading 1">Notes</Text-field>

<Text-field layout="Heading 2" style="Heading 2">The number of steps in the Euclidean algorithm</Text-field>

alpha := evalf((1 + 5^(1/2))/2): log[alpha](10^100);

NiMkIityPihceSUhIig=