[b]Main idea: [/b]The [i]Greatest Common Factor [/i]of two positive integers [math]a[/math] and [math]b[/math], is the largest counting number [math]d[/math], that divides both, [math]a[/math] and [math]b[/math].[br][b]Definition:[/b] [i]The [/i][b]Greatest Common Factor [/b]of two positive integers [math]a[/math] and [math]b[/math], is an integer [math]d[/math], such that:[br][list][*][i]divisibility condition:[/i] [math]d[/math] divides both a and b.[/*][*][i][url=https://www.merriam-webster.com/dictionary/maximal#:~:text=1%20%3A%20being%20an%20upper%20limit,Sentences%20Learn%20More%20About%20maximal]maximality [/url]condition[/i]: If there exists another integer [math]d'[/math] that divides both [math]a[/math] and [math]b[/math], then [math]d'[/math] divides [math]d[/math].[/*][/list][b]Notation: [/b]If [math]d[/math] is the [i]Greatest Common Factor[/i] of integers a and b, then we will write [math]d=gcf(a,b)[/math].

It works great for small integer numbers, but tends to be non efficient for large numbers.

It works great for small integer numbers whose factored form can be easily found, but tends to be non efficient for large numbers.

It works great in any case!

[b]Main idea:[/b] The [i]Least Common Multiple[/i] of two positive integers [math]a[/math] and [math]b[/math], is the largest counting number [math]m[/math], which can be divided by both, [math]a[/math] and [math]b[/math].[br][b]Definition:[/b] The [b]Least Common Multiple [/b]of two positive integers [math]a[/math] and [math]b[/math], is an integer [math]m[/math], such that:[br][i]divisibility condition[/i]: [math]m[/math] is divided by both [math]a[/math] and [math]b[/math].[br][i][url=https://www.merriam-webster.com/dictionary/minimality#:~:text=%3A%20the%20state%20or%20quality%20of%20being%20minimal]minimality[/url] condition[/i]: If there exists another integer [math]m'[/math] that is divided by both [math]a[/math] and [math]b[/math], then [math]m'[/math] is divided by [math]m[/math].[br][b]Notation:[/b] If m the [i]Least Common Multiple[/i] of integers a and b, then we will write [math]m=lcm(a,b)[/math].