Number of Integers and Integer Properties
Number of Integers and Integer Properties covers divisibility, the Euclidean algorithm, integer solutions, and base representation. These topics reward systematic division and careful handling of remainders.
Core rules
- If a=bq+r with 0≤r<b, then gcd(a,b)=gcd(b,r). Repeated division gives the Euclidean algorithm.
- Linear Diophantine ax+by=c has integer solutions only when gcd(a,b) divides c; one solution generates all solutions by adding multiples of b/g and subtracting multiples of a/g.
- In base b, digits range from 0 to b-1, and place values are powers of b. Convert by repeated division for integers, and by multiplying digits for expansion.
- The Euclidean algorithm terminates because remainders strictly decrease.
Worked example
Find gcd(1071,462). 1071=2·462+147; 462=3·147+21; 147=7·21+0. The last nonzero remainder is 21, so gcd=21. Since 21 divides 462, the equation 1071x+462y=21 has integer solutions; dividing by 21 reduces it to 51x+22y=1.
Traps
A remainder must be nonnegative and less than the divisor; for negative integers, adjust the quotient to satisfy this. Do not stop the Euclidean algorithm at the quotient-use the remainder. In base conversion, do not use a digit equal to or larger than the base. When reducing a Diophantine equation, divide the entire equation, including the constant.