Suppose that \(p\) is a prime number. How many numbers are there less than \(p^2\) that are relatively prime to \(p^2\)?
When we write \(137\) in decimal, we mean \(1 \times 10^2 + 3 \times 10 + 7 \times 1\). If we write it instead using powers of \(2\), we have \(137 = 1 \times 2^7 + 0 \times 2^6 + 0 \times 2^5 + 0 \times 2^4 + 1 \times 2^3 + 0 \times 2^2 + 0 \times 2^1 + 1 \times 2^0\). To tell apart binary representation from decimals, we can use the following notation: \(137 = (10001001)_2\).
What is the number \(273\) in binary? Note that using binary is useful for finding whether a particular Nim game is a winning position or a losing position.
Is it possible to construct a 485 × 6 table with the integers from 1 to 2910 such that the sum of the 6 numbers in each row is constant, and the sum of the 485 numbers in each column is also constant?
There is a very, very fast way of computing the greatest common divisor of two positive integers. It was in fact known even to the Greeks two thousand years ago. This procedure is called the Euclidean algorithm, named after Euclid, a famous ancient Greek mathematician.
The algorithm works as follows. Take two positive integers \(a,b\). Let’s say \(a\geq b\).
Calculate the remainder of \(a\) when divided by \(b\). Call it \(r_1\).
Calculate the remainder of \(b\) when divided by \(r_1\). Call it \(r_2\).
Calculate the remainder of \(r_1\) when divided by \(r_2\). Call it \(r_3\).
Continue to divide the remainder from two steps prior by the remainder from the last step, until...
The remainder \(r_n\) is divisible by \(r_{n+1}\). The Euclidean algorithm stops now and \(r_{n+1}\) is \(\gcd(a,b)\).
Show that there is indeed some natural number \(n\) such that \(r_n\) is divisible by \(r_{n+1}\), so that the Euclidean algorithm must stop eventually. Furthermore, show that \(r_{n+1}\) is actually \(\gcd(a,b)\) (otherwise it is all in vain!).
Let \(m\) and \(n\) be positive integers. What positive integers can be written as \(m+n+\gcd(m,n)+\text{lcm}(m,n)\), for some \(m\) and \(n\)?
Suppose that \(n\) is a natural number and \(p\) is a prime number. How many numbers are there less than \(p^n\) that are relatively prime to \(p^n\)?
Find the minimal natural number \(n>1\) such that \(n^6 - 2n^5 - n^4 + 4n^3 - n^2 - 2n +1\) is divisible by \(2025\).
What time is it going to be in \(2025\) hours from now?
Prove that the product of five consecutive integers is divisible by \(30\).
Prove that if \(n\) is a composite number, then \(n\) is divisible by some natural number \(x\) such that \(1 < x\leq \sqrt{n}\).