Your cart is empty
Number theory, divisibility
DEFINITION: For integers \latex{ a } and \latex{ b }, \latex{ a } is called a divisor of \latex{ b } if there exists an integer \latex{ c } for which \latex{a\times c = b.} It is denoted by \latex{a|b.}
DEFINITION: Positive integers with exactly two positive divisors are called prime numbers.
DEFINITION: Positive integers with more than two positive divisors are called composite numbers.
DEFINITION: Positive integers with exactly two positive divisors are called prime numbers.
DEFINITION: Positive integers with more than two positive divisors are called composite numbers.
DEFINITION: For two positive integers, the greatest one of their common divisors is called the greatest common divisor (\latex{ GCD }). The greatest common divisor of \latex{ a } and \latex{ b } is often denoted by (\latex{ a }; \latex{ b }) or \latex{ GCD }(\latex{ a }; \latex{ b }).
DEFINITION: For two positive integers, the smallest of their common multiples is called the least common multiple (\latex{ LCM }). The least common multiple of \latex{ a } and \latex{ b } is often denoted by \latex{\left[a;b\right]} or \latex{ LCM }(\latex{ a }; \latex{ b }).
THEOREM: There are infinitely many prime numbers.
THE FUNDAMENTAL THEOREM OF ARITHMETIC: Any composite number can be expressed as a product of prime numbers in a unique way, apart from the order of the factors.
DEFINITION: For two positive integers, the smallest of their common multiples is called the least common multiple (\latex{ LCM }). The least common multiple of \latex{ a } and \latex{ b } is often denoted by \latex{\left[a;b\right]} or \latex{ LCM }(\latex{ a }; \latex{ b }).
THEOREM: There are infinitely many prime numbers.
THE FUNDAMENTAL THEOREM OF ARITHMETIC: Any composite number can be expressed as a product of prime numbers in a unique way, apart from the order of the factors.
Example 1
Is it true that \latex{10^{2004}+8} is divisible by \latex{ 9 }?
Solution
Every power of \latex{ 10 } starts with the digit \latex{ 1 } and have as many zeros as the exponent. Thus \latex{10^{2,004}} begins with \latex{ 1 } and ends with \latex{ 2,004 } zeros. By adding \latex{ 8 } to this, the number will be \latex{ 100…008 }.
Since the sum of its digits is \latex{ 9 }, it follows that the sum itself is divisible by \latex{ 9 }.
Since the sum of its digits is \latex{ 9 }, it follows that the sum itself is divisible by \latex{ 9 }.
Example 2
Prove that \latex{5^{2004}+7} is not a prime.
Solution
Every exponent of \latex{ 5 } ends with the digit \latex{ 5 }, thus \latex{5^{2004}} also has this property.
By adding \latex{ 7 } to such a number the result will end in \latex{ 2 }, so it will be even.
As the only even prime number is \latex{ 2 } and \latex{5^{2004}+7\gt 2,} it is a composite number.
By adding \latex{ 7 } to such a number the result will end in \latex{ 2 }, so it will be even.
As the only even prime number is \latex{ 2 } and \latex{5^{2004}+7\gt 2,} it is a composite number.
Example 3
Find the positive integer \latex{ b } for which
\latex{(a;b)=12, \left[a;b\right]=720} and \latex{a=36.}
Solution
Find the prime factorization of the three numbers:
\latex{12=2^{2}\times 3; 720=2^{4}\times 3^{2}\times 5; 36=2^{2}\times 3^{2}.}
We have to find the canonical representation of \latex{ b }: its prime divisors are \latex{ 2 }, \latex{ 3 } and \latex{ 5 }.
The greatest common divisor consists of the common prime divisors of the two numbers to the smallest power occurring.
The greatest common divisor consists of the common prime divisors of the two numbers to the smallest power occurring.
Also, the least common multiple consists of the prime divisors of at least one of the numbers to the greatest power occurring.
It follows from the above that in the prime factorization of \latex{ b }, the exponent of \latex{ 2 } is \latex{ 4 }, the exponent of \latex{ 3 } is \latex{ 1 } and the exponent of \latex{ 5 } is also \latex{ 1 }. Therefore \latex{b=2^{4}\times 3\times 5=240.}
It follows from the above that in the prime factorization of \latex{ b }, the exponent of \latex{ 2 } is \latex{ 4 }, the exponent of \latex{ 3 } is \latex{ 1 } and the exponent of \latex{ 5 } is also \latex{ 1 }. Therefore \latex{b=2^{4}\times 3\times 5=240.}
\latex{ 1\\2\\ 6\\ 3\\ 1 }
\latex{ 2\\ 2\\ 3 }
\latex{ 720\\ 360\\ 180\\ 90\\ 45\\ 15\\ 5\\ 1 }
\latex{ 2\\ 2\\ 2\\ 2\\ 3\\ 3\\ 5 }
\latex{ 36\\ 18\\ 9\\ 3\\ 1 }
\latex{ 2\\ 2\\ 3\\ 3 }
Example 4
For which natural numbers \latex{ n } will the fraction \latex{\frac{n+13}{n-5}} be a natural number?
Solution
Transform the fraction so that the denominator is expressed in the numerator and then divide each term:
\latex{\frac{n+13}{n-5}=\frac{n-5+5+13}{n-5}=\frac{(n-5)+18}{n-5}=1+\frac{18}{n-5}.}
The resulting fraction will be a natural number if \latex{n-5} is a divisor of \latex{ 18 }.
Possible values of \latex{n – 5} are:
\latex{1;\,2;\,3;\,6;\,9;\,18.}
The corresponding values of \latex{ n } are:
\latex{6;\,7;\,8;\,11;\,14;\,23.}
In these cases the fraction equals to, respectively,
\latex{19;\,10;\,7;\,4;\,3;\,2.}
Example 5
Transform the quaternary number \latex{ 1,233 } into decimal form.
Solution
\latex{1,233_{4}=1\times 4^{3}+2\times 4^{2}+3\times 4+3=111.}
Example 6
Transform the decimal number \latex{ 1,988 } into octal form.
Solution
Perform the following Euclidean divisions:
\latex{1988\div 8=248,} the remainder is \latex{ 4 };
\latex{248\div 8=31,} the remainder is \latex{ 0 };
\latex{31\div 8=3,} the remainder is \latex{ 7 };
\latex{3\div 8=0,} the remainder is \latex{ 3 }.
\latex{248\div 8=31,} the remainder is \latex{ 0 };
\latex{31\div 8=3,} the remainder is \latex{ 7 };
\latex{3\div 8=0,} the remainder is \latex{ 3 }.
Therefore \latex{1,988=3,704_{8}.}
Exercises
{{exercise_number}}. Express the following numbers as a product of powers of primes: \latex{35^{7}\times 80^{4}\times 28^{3}.}
{{exercise_number}}. Is \latex{10^{2,004}+11} a prime?
{{exercise_number}}. Is there a prime followed by exactly \latex{ 10 } composite numbers in the sequence of natural numbers?
{{exercise_number}}. Decide whether the product of \latex{ 25 } subsequent numbers will always be divisible by \latex{ 2,004 } or not. Verify your answer!
{{exercise_number}}. Transform the number corresponding to the year of your birth to
- binary form,
- senary form.
{{exercise_number}}. Tim says that \latex{ 1,526 } is smaller than \latex{ 1,000 }. Which number system is \latex{ 1,526 } written in, if \latex{ 1,000 } is in decimal form?
{{exercise_number}}. Determine the four digit number \latex{\overline{abcd}} for which
\latex{\overline{abcd}+\overline{abc} +\overline{ab}+\overline{a}=2,004.}
{{exercise_number}}. Find all integers \latex{ n } for which \latex{2n^{2}-n-36} is the square of a prime.