Question

Find the g.c.d of 144,233. \[\]

Answer 1

Hint: We find all the factors of 144 and 233 from the prime factorization 144 and 233. We first find all possible prime factors of $n$ under $\sqrt{n}$. We check the divisibility of each prime less than $\sqrt{n}$ to find the prime factors and then find the prime factorization. The greatest of the common factors that appear in the factors of 144 and 233 is the gcd.\[\]

Complete step by step answer:
We know that the greatest common divisor abbreviated as g.c.d. of two numbers is the divisor that exactly divides both the number and is greater than any other divisor that does the same. The exact divisor is also called factor and g.c.d. is also called highest common factor (HCF).\[\]
We know that a number $n$ can be expressed as a product of prime factors with say $k$ primes ${{p}_{1}},{{p}_{2}},...,{{p}_{k}}$ as
\[n={{p}_{1}}^{{{e}_{1}}}\times {{p}_{1}}^{{{e}_{1}}}...{{p}_{k}}^{{{e}_{k}}}\]
Here the exponents ${{e}_{1}},{{e}_{2}},...,{{e}_{k}}$ are positive integers. We can find all the composite and prime factors of a composite number from the factorization which leaves only one factor that is 1. The factor of a prime number is the number itself and 1. We know that all prime factors of natural number $n$ appear before $\sqrt{n}$ which means
\[{{p}_{1}},{{p}_{2}},...,{{p}_{k}}<\sqrt{n}\]
We are asked to find the gcd of 144 and 233. Let us first find the factors of 144. We have $\sqrt{144}=12$ which means the primes that may divide 144 are 2, 3, 5, 7, 11. Let us first divide 144 by 2 and we find the prime factorization
\[\begin{align}
  & 2\left| \!{\underline {\,
  144 \,}} \right. \\
 & 2\left| \!{\underline {\,
  72 \,}} \right. \\
 & 2\left| \!{\underline {\,
  36 \,}} \right. \\
 & 2\left| \!{\underline {\,
  18 \,}} \right. \\
 & 3\left| \!{\underline {\,
  9 \,}} \right. \\
 & \hspace{0.5 cm}3 \\
\end{align}\]
So the prime factorization of 144 is
\[144=2\times 2\times 2\times 2\times 3\times 3={{2}^{4}}\times {{3}^{2}}\]
We can find the factors taking the product of any combination 2 and 3 with their powers. So the factors of 144 are
\[\begin{align}
  & F\left( 144 \right)=1,2,3,2\times 2,2\times 3,2\times 2\times 2,3\times 3,2\times 2\times 3,2\times 2\times 2\times 2,2\times 2\times 2\times 3, \\
 & 2\times 2\times 3\times 3,2\times 2\times 2\times 2\times 3,2\times 2\times 2\times 3\times 3,2\times 2\times 2\times 2\times 3\times 3 \\
 & \Rightarrow F\left( 144 \right)=1,2,3,4,6,8,9,12,16,18,24,36,48,72,144 \\
\end{align}\]

Now we shall find the factors 233. We have $\sqrt{233}<15.2$. So 233 may be divisible by any of the primes that come before 15.2 which are 2, 3, 5, 7, 11, and 13. We check whether these primes exactly divide 233 either by dividing or by divisibility rules. We find that the 233 is not divisible by any prime before $\sqrt{233}$ and hence is a prime whose factors are
\[F\left( 233 \right)=1,233\]
We check the factors of 144 and 233 and find only one common factor which is 1. So we have the greatest common divisor as
\[\gcd \left( 144,233 \right)=1\]

Note: We note that the divisibility rule is a type of rule using we which we check the divisibility by prime factors, for example if unit digit of a composite number is even then 2 is factor. The total number of divisors of a number is given by $\left( {{e}_{1}}+1 \right)\left( {{e}_{2}}+1 \right)...\left( {{e}_{k}}+1 \right)$.