cong

PROBLEMS ON CONGRUENCES AND
DIVISIBILITY
1. Do there exist 1,000,000 consecutive integers each of which contains a

repeated prime factor?
2. A positive integer n is powerful if for every prime p dividing n, we have

that p2 divides n. Show that for any k ≥ 1 there exist k consecutive
integers, none of which is powerful.
3. Show that for any k ≥ 1 there exist k consecutive positive integers,

none of which is a sum of two squares. (You may use the fact that a
positive integer n is a sum of two squares if and only if for every prime
p ≡ 3 (mod 4), the largest power of p dividing n is an even power of p.)
4. Prove that every positive integer has a multiple whose decimal repre-
sentation involves all ten digits.
5. Prove that among any ten consecutive integers at least one is relatively
prime to each of the others.
6. Find the length of the longest sequence of equal nonzero digits in which
an integral square can terminate (in base 10), and find the smallest
square which terminates in such a sequence.
7. Show that if n is an integer greater than 1, then n does not divide

2n − 1.
8. Show that if n is an odd integer greater than 1, then n does not divide
2n + 2.
9. (a) Prove that pa ≡ ab (mod p) for all integers p, a, and b with p a

pb
prime, p > 0, and a ≥ b ≥ 0.
(b) Show in fact that the above congruence holds modulo p2 .
(c) Show that if p ≥ 5, then the above congruence even holds modulo
p3 .
1
10. Let n1 , n2 , . . . , ns be distinct integers such that
(n1 + k)(n2 + k) · · · (ns + k)
is an integral multiple of n1 n2 · · · ns for every integer k. For each of the

following assertions, give a proof or a counterexample:
(a) |ni | = 1 for some i.
(b) If further all ni are positive, then
{n1 , n2 , . . . , ns } = {1, 2, . . . , s}.
11. Let p be in the set {3, 5, 7, 11, . . . } of odd primes, and let
F (n) = 1 + 2n + 3n2 + · · · + (p − 1)np−2 .
Prove that if a and b are distinct integers in {0, 1, 2, . . . , p − 1} then

F (a) and F (b) are not congruent modulo p, that is, F (a) − F (b) is not
exactly divisible by p.
12. Define a sequence {ai } by a1 = 3 and ai+1 = 3ai for i ≥ 1. Which
integers between 00 and 99 inclusive occur as the last two digits in the
decimal expansion of infinitely many ai ?
13. What is the units (i.e., rightmost) digit of
1020000

?
10100 + 3
Here [x] is the greatest integer ≤ x.
14. Suppose p is an odd prime. Prove that
p
X p p+j
≡ 2p + 1 (mod p2 ).
j=0
j j
15. If p is a prime number greater than 3 and k = b2p/3c, prove that the
sum
p p p
+ + ··· +
1 2 k
of binomial coefficients is divisible by p2 .
2
16. Prove that for n ≥ 2,
n terms n−1 terms
z}|{ z}|{
···2 ···2
22 ≡ 22 (mod n).
17. The sequence (an )n≥1 is defined by a1 = 1, a2 = 2, a3 = 24, and, for

n ≥ 4,
6a2n−1 an−3 − 8an−1 a2n−2
an = .
an−2 an−3
Show that, for all n, an is an integer multiple of n.
18. Prove that the expression

gcd(m, n) n
n m
is an integer for all pairs of integers n ≥ m ≥ 1.
19. Show that for each positive integer n,
n
Y
n! = lcm{1, 2, . . . , bn/ic}.
i=1
(Here lcm denotes the least common multiple, and bxc denotes the
greatest integer ≤ x.)
20. Define a sequence {un }∞
n=0 by u0 = u1 = u2 = 1, and thereafter by the
condition that
un un+1
det = n!
un+2 un+3
for all n ≥ 0. Show that un is an integer for all n. (By convention,
0! = 1.)
21. Let p be a prime number. Let h(x) be a polynomial with integer coeffi-
cients such that h(0), h(1), . . . , h(p2 − 1) are distinct modulo p2 . Show
that h(0), h(1), . . . , h(p3 − 1) are distinct modulo p3 .
22. How many coefficients of the polynomial
Y
Pn (x1 , . . . , xn ) = (xi + xj )
1≤i<j≤n
are odd?
3
23. Define a0 = a1 = a2 = a3 = 1,
an+4 an = an+3 an+1 + a2n+2 , n ≥ 0.
Is an is an integer for all n ≥ 0?
24. Define a0 = a1 = 1 and

n−1
1 X 2
an = a , n > 1.
n − 1 i=0 i
Is an an integer for all n ≥ 0?
25. Do there exist positive integers a and b with b − a > 1 such for every
a < k < b, either gcd(a, k) > 1 or gcd(b, k) > 1?
26. Let f (x) = a0 + a1 x + · · · be a power series with integer coefficients,

with a0 6= 0. Suppose that the power series expansion of f 0 (x)/f (x) at
x = 0 also has integer coefficients. Prove or disprove that a0 |an for all
n ≥ 0.
27. Suppose that f (x) and g(x) are polynomials (with f (x) not identically
0) taking integers to integers such that for all n ∈ Z, either f (n) = 0 or
f (n)|g(n). Show that f (x)|g(x), i.e., there is a polynomial h(x) with
rational coefficients such that g(x) = f (x)h(x).
28. Let S be a set of rational numbers such that
(a) 0 ∈ S;
(b) If x ∈ S then x + 1 ∈ S and x − 1 ∈ S; and
(c) If x ∈ S and x 6∈ {0, 1}, then 1/(x(x − 1)) ∈ S.
Must S contain all rational numbers?

10n n
29. Prove that for each positive integer n, the number 1010 + 1010 +
10n − 1 is not prime.
30. Let p be an odd prime. P Showk that for at least (p + 1)/2 values of n in
{0, 1, 2, . . . , p − 1}, p−1
k=0 k!n is not divisible by p.
4
31. Let a and b be rational numbers such that an − bn is an integer for all
positive integers n. Prove or disprove that a and b must themselves be
integers.
32. Find the smallest integer n ≥ 2 for which there exists an integer m
with the following property: for each i ∈ {1, . . . , n}, there exists j ∈
{1, . . . , n} different from i such that gcd(m + i, m + j) > 1.
33. True or false? For every positive integer n there exists a positive integer
k for which n|Fk , where Fk denotes a Fibonacci number.

cong

Uploaded by

Copyright:

Available Formats

cong

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

cong

Uploaded by

Copyright:

Available Formats

PROBLEMS ON CONGRUENCES AND

1. Do there exist 1,000,000 consecutive integers each of which contains a

2. A positive integer n is powerful if for every prime p dividing n, we have

3. Show that for any k ≥ 1 there exist k consecutive positive integers,

7. Show that if n is an integer greater than 1, then n does not divide

9. (a) Prove that pa ≡ ab (mod p) for all integers p, a, and b with p a

(n1 + k)(n2 + k) · · · (ns + k)

is an integral multiple of n1 n2 · · · ns for every integer k. For each of the

{n1 , n2 , . . . , ns } = {1, 2, . . . , s}.

F (n) = 1 + 2n + 3n2 + · · · + (p − 1)np−2 .

Prove that if a and b are distinct integers in {0, 1, 2, . . . , p − 1} then

17. The sequence (an )n≥1 is defined by a1 = 1, a2 = 2, a3 = 24, and, for

an+4 an = an+3 an+1 + a2n+2 , n ≥ 0.

Is an is an integer for all n ≥ 0?

24. Define a0 = a1 = 1 and

Is an an integer for all n ≥ 0?

26. Let f (x) = a0 + a1 x + · · · be a power series with integer coefficients,

28. Let S be a set of rational numbers such that

Must S contain all rational numbers?

You might also like