Practice
Prove that \(n^2+n\) is even for every integer \(n\).
Factor out \(n\).
\(n^2+n=n(n+1)\). Of two consecutive integers, one is even, so the product is even.
Find the last digit of \(2^{2026}\).
The last digits of powers of \(2\) cycle as \(2,4,8,6\).
Since \(2026\equiv2\pmod4\), the last digit is \(4\).
Prove that any two consecutive odd numbers are coprime or have GCD \(2\)? Correct the statement and prove the true version.
Two odd numbers cannot be consecutive integers; likely the intended numbers differ by \(2\).
Correct statement: two odd numbers differing by \(2\) are coprime. Let the numbers be \(n\) and \(n+2\), with \(n\) odd. Their common divisor divides \(2\). Since both numbers are odd, the common divisor is not divisible by \(2\). Hence the GCD is \(1\).
Which residues can an integer square have modulo \(3\)?
Check \(0,1,2\).
If \(n\equiv0,1,2\pmod3\), then \(n^2\equiv0,1,1\pmod3\). Only \(0\) and \(1\) are possible.
Find the digit \(x\) if \(72x5\) is divisible by \(9\).
The digit sum must be divisible by \(9\).
The digit sum is \(7+2+x+5=14+x\). We need \(14+x\equiv0\pmod9\). Since \(x\) is a digit, \(x=4\).
Prove that \(24\mid n(n+1)(n+2)(n+3)\) for every integer \(n\).
Prove divisibility by \(8\) and by \(3\).
Among four consecutive integers, one is divisible by \(3\). Also there are two even numbers, one of which is divisible by \(4\), so the product is divisible by \(8\). Since \(8\) and \(3\) are coprime, the product is divisible by \(24\).
Solve \(xy+x+y=47\) in positive integers.
Add \(1\).
We get \((x+1)(y+1)=48\). Factor pairs of \(48\) greater than \(1\) give \((x,y)=(1,23),(2,15),(3,11),(5,7),(7,5),(11,3),(15,2),(23,1)\).
Find \(\gcd(n^2+n+1,n+1)\).
Replace \(n\) by \(-1\) modulo \(n+1\).
Modulo \(n+1\), \(n\equiv-1\). Then \(n^2+n+1\equiv1-1+1=1\). Hence the common divisor divides \(1\), so the GCD is \(1\).
Prove that \(x^2=3y^2\) has no positive integer solutions.
If \(3\mid x^2\), then \(3\mid x\).
From \(x^2=3y^2\), we get \(3\mid x^2\), hence \(3\mid x\). Let \(x=3t\). Then \(9t^2=3y^2\), so \(y^2=3t^2\), hence \(3\mid y\). This gives a smaller solution \((t,\frac{y}{3})\). Repeating gives infinite divisibility by \(3\), impossible for positive integers.
Find all positive integers \(n\) such that \(n+3\mid n^2+2\).
Modulo \(n+3\): \(n\equiv-3\).
We have \(n^2+2\equiv9+2=11\pmod{n+3}\). Hence \(n+3\mid11\). Since \(n\ge1\), \(n+3\ge4\), so \(n+3=11\), \(n=8\). Check works.
Find the last two digits of \(11^{2025}\).
Check the pattern of \(11^k\pmod{100}\).
For \(k=1,\ldots,10\), we get \(11,21,31,\ldots,91,01\), a cycle of length \(10\). Since \(2025\equiv5\pmod{10}\), the last two digits are \(51\).
Solve the system \(n\equiv2\pmod5\), \(n\equiv3\pmod7\).
Let \(n=5k+2\).
Substitute: \(5k+2\equiv3\pmod7\), so \(5k\equiv1\pmod7\). The inverse of \(5\) modulo \(7\) is \(3\), hence \(k\equiv3\pmod7\). Thus \(n=5(7t+3)+2=35t+17\).
Find all \(n\pmod3\) for which \(3\mid n^2+n+1\).
Check residues \(0,1,2\).
For \(n\equiv0\), we get \(1\); for \(n\equiv1\), we get \(3\equiv0\); for \(n\equiv2\), we get \(7\equiv1\pmod3\). Thus only \(n\equiv1\pmod3\) works.
Let an odd prime \(p\) divide \(a^2+1\). Prove that \(p\equiv1\pmod4\).
From \(a^2\equiv-1\pmod p\), it follows that \(a^4\equiv1\pmod p\).
Since \(p\mid a^2+1\), we have \(a^2\equiv-1\pmod p\). Then \(a^4\equiv1\pmod p\), but \(a^2 ot\equiv1\pmod p\). Thus the order of \(a\) modulo \(p\) is \(4\). The order divides \(p-1\), hence \(4\mid p-1\), so \(p\equiv1\pmod4\).
Find all positive integers \(n\) such that \(2n-1\mid n^2+1\).
Multiply by \(4\).
Let \(d=2n-1\). If \(d\mid n^2+1\), then \(d\mid4(n^2+1)\). But \(4(n^2+1)=d^2+2d+5\). Thus \(d\mid5\). Hence \(d=1\) or \(5\), giving \(n=1\) or \(n=3\). Both work.
Find all positive integers \(x>y\) such that \(x^2-y^2=840\).
Set \(x-y=2u\), \(x+y=2v\).
Since \(x-y\) and \(x+y\) have the same parity and their product is \(840\), both factors are even. Let \(x-y=2u\), \(x+y=2v\). Then \(uv=210\), \(u
Prove that \(5\mid2^{4n}-1\) for every positive integer \(n\).
Find \(2^4\pmod5\).
Since \(2^4=16\equiv1\pmod5\), \(2^{4n}=(2^4)^n\equiv1^n\equiv1\pmod5\). Hence \(5\mid2^{4n}-1\).
Let \(\gcd(m,10)=1\). Prove that there exists a number consisting only of digits \(0\) and \(1\) that is divisible by \(m\).
It is enough to construct a number of only ones.
By the pigeonhole principle, among \(R_1,\ldots,R_m\), either one is divisible by \(m\), or two have the same residue. In the second case their difference is \(10^iR_j\) for some \(j\) and is divisible by \(m\). Since \(10^i\) is invertible modulo \(m\), \(m\mid R_j\). The number \(R_j\) consists only of ones, hence only of digits \(0\) and \(1\).
Describe all positive integers with exactly \(6\) positive divisors.
Use \( au(n)=(\alpha_1+1)\cdots(\alpha_s+1)\).
If \(n=p_1^{\alpha_1}\cdots p_s^{\alpha_s}\), then \( au(n)=(\alpha_1+1)\cdots(\alpha_s+1)\). We need \(6\). The possibilities are \(6=6\) and \(6=3\cdot2\). Hence \(n=p^5\) or \(n=p^2q\), where \(p,q\) are distinct primes.
Prove that if the square of a positive integer ends in digit \(5\), then its last two digits are \(25\).
A number whose square ends in \(5\) itself ends in \(5\).
Let the number be \(10a+5\). Then \((10a+5)^2=100a^2+100a+25=100a(a+1)+25\). Thus the last two digits of the square are \(25\).
Let \(n\) be an odd positive integer. Prove that \(n\mid1^n+2^n+\cdots+(n-1)^n\).
Group \(a\) with \(n-a\).
For each \(a=1,\ldots,n-1\), the number \(n-a\) also appears. Since \(n\) is odd, \(a^n+(n-a)^n\equiv a^n+(-a)^n=0\pmod n\). All terms split into such pairs, so the whole sum is divisible by \(n\).
Find all primes \(p\) such that \(p\mid2^p+1\).
For an odd prime, use Fermat's little theorem.
For \(p=2\), \(2^2+1=5\), not divisible by \(2\). Let \(p\) be odd. By Fermat's little theorem, \(2^p\equiv2\pmod p\). Then \(2^p+1\equiv3\pmod p\). Thus \(p\mid3\), so \(p=3\). Check: \(3\mid9\).
Prove that there are infinitely many numbers consisting only of digits \(0\) and \(1\) that are divisible by \(2027\).
First build one multiple of ones, then append zeros on the right.
Since \(\gcd(2027,10)=1\), there exists a repunit \(R_s\) divisible by \(2027\). Then for every \(t\ge0\), the number \(R_s\cdot10^t\) is also divisible by \(2027\) and consists of ones followed by zeros. Different \(t\) give infinitely many different numbers.
Prove that for every \(k\ge1\), there exist \(k\) consecutive positive integers, each divisible by the square of some prime.
Choose distinct primes \(p_1,\ldots,p_k\) and impose \(n+i\equiv0\pmod{p_i^2}\).
Choose distinct primes \(p_1,\ldots,p_k\). Consider the system \(n\equiv-1\pmod{p_1^2}\), \(n\equiv-2\pmod{p_2^2}\), \(\ldots\), \(n\equiv-k\pmod{p_k^2}\). The moduli \(p_i^2\) are pairwise coprime, so CRT gives a solution \(n_0\). Then each \(n_0+i\) is divisible by \(p_i^2\). Adding a sufficiently large multiple of \(p_1^2\cdots p_k^2\) to \(n_0\), we obtain positive consecutive integers.