AoPS Community PEN A Problems

Divisibility Theory
www.artofproblemsolving.com/community/c3588
by Peter, Hawk Tiger, Naphthalin, ideahitme, Ilthigore, ZetaX, TTsphn, TomciO, Leonhard Euler, Euler-ls,
Tiks, mathmanman, Vaf, rem, freemind, Rust, tim1234133, PhilAndrew, Yimin Ge, s.tringali

1 Show that if x, y, z are positive integers, then (xy + 1)(yz + 1)(zx + 1) is a perfect square if and
only if xy + 1, yz + 1, zx + 1 are all perfect squares.

2 Find infinitely many triples (a, b, c) of positive integers such that a, b, c are in arithmetic pro-
gression and such that ab + 1, bc + 1, and ca + 1 are perfect squares.

3 Let a and b be positive integers such that ab + 1 divides a2 + b2 . Show that

a2 + b2
ab + 1
is the square of an integer.

4 If a, b, c are positive integers such that

0 < a2 + b2 − abc ≤ c,

show that a2 + b2 − abc is a perfect square.

5 Let x and y be positive integers such that xy divides x2 + y 2 + 1. Show that

x2 + y 2 + 1
= 3.
xy

6 - Find infinitely many pairs of integers a and b with 1 < a < b, so that ab exactly divides
a2 + b2 − 1. - With a and b as above, what are the possible values of

a2 + b2 − 1
?
ab

√ √
7 Let n be a positive integer such that 2 + 2 28n2 + 1 is an integer. Show that 2 + 2 28n2 + 1 is
the square of an integer.

8 The integers a and b have the property that for every nonnegative integer n the number of
2n a + b is the square of an integer. Show that a = 0.

© 2019 AoPS Incorporated 1

AoPS Community PEN A Problems

9 Prove that among any ten consecutive positive integers at least one is relatively prime to the
product of the others.

10 Let n be a positive integer with n ≥ 3. Show that

nn n
nn − nn

is divisible by 1989.

11 Let a, b, c, d be integers. Show that the product

(a − b)(a − c)(a − d)(b − c)(b − d)(c − d)

is divisible by 12.

12 Let k, m, and n be natural numbers such that m + k + 1 is a prime greater than n + 1. Let
cs = s(s + 1). Prove that the product

(cm+1 − ck )(cm+2 − ck ) · · · (cm+n − ck )

is divisible by the product c1 c2 · · · cn .

13 Show that for all prime numbers p,

p−1
Y
Q(p) = k 2k−p−1
k=1

is an integer.

14 Let n be an integer with n ≥ 2. Show that n does not divide 2n − 1.

15 Suppose that k ≥ 2 and n1 , n2 , · · · , nk ≥ 1 be natural numbers having the property

n2 | 2n1 − 1, n3 | 2n2 − 1, · · · , nk | 2nk−1 − 1, n1 | 2nk − 1.

Show that n1 = n2 = · · · = nk = 1.

16 Determine if there exists a positive integer n such that n has exactly 2000 prime divisors and
2n + 1 is divisible by n.

17 Let m and n be natural numbers such that

(m + 3)n + 1
A=
3m
is an integer. Prove that A is odd.

© 2019 AoPS Incorporated 2

AoPS Community PEN A Problems

18 Let m and n be natural numbers and let mn + 1 be divisible by 24. Show that m + n is divisible
by 24.

19 Let f (x) = x3 + 17. Prove that for each natural number n ≥ 2, there is a natural number x for
which f (x) is divisible by 3n but not 3n+1 .

20 Determine all positive integers n for which there exists an integer m such that 2n − 1 divides
m2 + 9.

21 Let n be a positive integer. Show that the product of n consecutive positive integers is divisible
by n!

22 Prove that the number

n  
X 2n + 1 3k
2
2k + 1
k=0

is not divisible by 5 for any integer n ≥ 0.

23 (Wolstenholme’s Theorem) Prove that if

1 1 1
1+ + + ··· +
2 3 p−1

is expressed as a fraction, where p ≥ 5 is a prime, then p2 divides the numerator.

24 Let p > 3 is a prime number and k = b 2p

3 c. Prove that
     
p p p
+ + ··· +
1 2 k

is divisible by p2 .

Show that 2n
| lcm(1, 2, · · · , 2n) for all positive integers n.


25 n

26 Let m and n be arbitrary non-negative integers. Prove that

(2m)!(2n)!
m!n!(m + n)!

is an integer.

27 Show that the coefficients of a binomial expansion (a + b)n where n is a positive integer, are
all odd, if and only if n is of the form 2k − 1 for some positive integer k.

© 2019 AoPS Incorporated 3

AoPS Community PEN A Problems

28 Prove that the expression  

gcd(m, n) n
n m
is an integer for all pairs of positive integers (m, n) with n ≥ m ≥ 1.

29 For which positive integers k, is it true that there are infinitely many pairs of positive integers
(m, n) such that
(m + n − k)!
m! n!
is an integer?

30 Show that if n ≥ 6 is composite, then n divides (n − 1)!.

31 Show that there exist infinitely many positive integers n such that n2 + 1 divides n!.

32 Let a and b be natural numbers such that

a 1 1 1 1 1
= 1 − + − + ··· − + .
b 2 3 4 1318 1319
Prove that a is divisible by 1979.

33 Let a, b, x ∈ N with b > 1 and such that bn − 1 divides a. Show that in base b, the number a has
at least n non-zero digits.

34 Let p1 , p2 , · · · , pn be distinct primes greater than 3. Show that

2p1 p2 ···pn + 1
has at least 4n divisors.

35 Let p ≥ 5 be a prime number. Prove that there exists an integer a with 1 ≤ a ≤ p − 2 such that
neither ap−1 − 1 nor (a + 1)p−1 − 1 is divisible by p2 .
j k
(n−1)!
36 Let n and q be integers with n ≥ 5, 2 ≤ q ≤ n. Prove that q − 1 divides q .

37 If n is a natural number, prove that the number (n + 1)(n + 2) · · · (n + 10) is not a perfect square.

38 Let p be a prime with p > 5, and let S = {p − n2 |n ∈ N, n2 < p}. Prove that S contains two
elements a and b such that a|b and 1 < a < b.

39 Let n be a positive integer. Prove that the following two statements are equivalent. - n is not
divisible by 4 - There exist a, b ∈ Z such that a2 + b2 + 1 is divisible by n.

© 2019 AoPS Incorporated 4

AoPS Community PEN A Problems

40 Determine the greatest common divisor of the elements of the set

{n13 − n | n ∈ Z}.

41 Show that there are infinitely many composite numbers n such that 3n−1 − 2n−1 is divisible by
n.

42 Suppose that 2n + 1 is an odd prime for some positive integer n. Show that n must be a power
of 2.

43 Suppose that p is a prime number and is greater than 3. Prove that 7p − 6p − 1 is divisible by
43.

44 Suppose that 4n + 2n + 1 is prime for some positive integer n. Show that n must be a power
of 3.

45 Let b, m, n ∈ N with b > 1 and m 6= n. Suppose that bm − 1 and bn − 1 have the same set of
prime divisors. Show that b + 1 must be a power of 2.

46 Let a and b be integers. Show that a and b have the same parity if and only if there exist integers
c and d such that a2 + b2 + c2 + 1 = d2 .

47 Let n be a positive integer with n > 1. Prove that

1 1
+ ··· +
2 n
is not an integer.

48 Let n be a positive integer. Prove that

1 1
+ ··· +
3 2n + 1
is not an integer.

49 Prove that there is no positive integer n such that, for k = 1, 2, · · · , 9, the leftmost digit of
(n + k)! equals k.

50 Show that every integer k > 1 has a multiple less than k 4 whose decimal expansion has at
most four distinct digits.

51 Let a, b, c and d be odd integers such that 0 < a < b < c < d and ad = bc. Prove that if a+d = 2k
and b + c = 2m for some integers k and m, then a = 1.

© 2019 AoPS Incorporated 5

AoPS Community PEN A Problems

52 Let d be any positive integer not equal to 2, 5, or 13. Show that one can find distinct a and b in
the set {2, 5, 13, d} such that ab − 1 is not a perfect square.

53 Suppose that x, y, and z are positive integers with xy = z 2 + 1. Prove that there exist integers
a, b, c, and d such that x = a2 + b2 , y = c2 + d2 , and z = ac + bd.

54 A natural number n is said to have the property P , if whenever n divides an −1 for some integer
a, n2 also necessarily divides an − 1. - Show that every prime number n has the property P . -
Show that there are infinitely many composite numbers n that possess the property P .

55 Show that for every natural number n the product

     
2 2 2 2
4− 4− 4− ··· 4 −
1 2 3 n
is an integer.

56 Let a, b, and c be integers such that a + b + c divides a2 + b2 + c2 . Prove that there are infinitely
many positive integers n such that a + b + c divides an + bn + cn .

57 Prove that for every n ∈ N the following proposition holds: 7|3n + n3 if and only if 7|3n n3 + 1.

58 Let k ≥ 14 be an integer, and let pk be the largest prime number which is strictly less than k.
You may assume that pk ≥ 3k 4 . Let n be a composite integer. Prove that - if n = 2pk , then n
does not divide (n − k)!, - if n > 2pk , then n divides (n − k)!.

59 Suppose that n has (at least) two essentially distinct representations as a sum of two squares.
Specifically, let n = s2 + t2 = u2 + v 2 , where s ≥ t ≥ 0, u ≥ v ≥ 0, and s > u. Show that
gcd(su − tv, n) is a proper divisor of n.

60 Prove that there exist an infinite number of ordered pairs (a, b) of integers such that for every
positive integer t, the number at+b is a triangular number if and only if t is a triangular number.

61 For any positive integer n > 1, let p(n) be the greatest prime divisor of n. Prove that there are
infinitely many positive integers n with
p(n) < p(n + 1) < p(n + 2).

62 Let p(n) be the greatest odd divisor of n. Prove that

2 n
1 X p(k) 2
> .
2n k 3
k=1

© 2019 AoPS Incorporated 6

AoPS Community PEN A Problems

63 There is a large pile of cards. On each card one of the numbers 1, 2, · · · , n is written. It is known
that the sum of all numbers of all the cards is equal to k · n! for some integer k. Prove that it
is possible to arrange cards into k stacks so that the sum of numbers written on the cards in
each stack is equal to n!.

64 The last digit of the number x2 + xy + y 2 is zero (where x and y are positive integers). Prove
that two last digits of this numbers are zeros.

65 Clara computed the product of the first n positive integers and Valerid computed the product
of the first m even positive integers, where m ≥ 2. They got the same answer. Prove that one
of them had made a mistake.

66 (Four Number Theorem) Let a, b, c, and d be positive integers such that ab = cd. Show that
there exists positive integers p, q, r, s such that
a = pq, b = rs, c = ps, d = qr.

Prove that 2n
is divisible by n + 1.


67 n

68 Suppose that S = {a1 , · · · , ar } is a set of positive integers, and let Sk denote the set of subsets
of S with k elements. Show that
r Y
i
gcd(s)((−1) ) .
Y
lcm(a1 , · · · , ar ) =
i=1 s∈Si

69 Prove that if the odd prime p divides ab − 1, where a and b are positive integers, then p appears
to the same power in the prime factorization of b(ad − 1), where d = gcd(b, p − 1).

70 Suppose that m = nq, where n and q are positive integers. Prove that the sum of binomial
coefficients
n−1
X gcd(n, k)q 
gcd(n, k)
k=0
is divisible by m.

71 Determine all integers n > 1 such that

2n + 1
n2
is an integer.

© 2019 AoPS Incorporated 7

AoPS Community PEN A Problems

72 Determine all pairs (n, p) of nonnegative integers such that - p is a prime, - n < 2p, - (p − 1)n + 1
is divisible by np−1 .

73 Determine all pairs (n, p) of positive integers such that - p is a prime, n > 1, - (p − 1)n + 1 is
divisible by np−1 .

74 Find an integer n, where 100 ≤ n ≤ 1997, such that

2n + 2
n
is also an integer.

75 Find all triples (a, b, c) of positive integers such that 2c − 1 divides 2a + 2b + 1.

76 Find all integers a, b, c with 1 < a < b < c such that

(a − 1)(b − 1)(c − 1) is a divisor of abc − 1.

77 Find all positive integers, representable uniquely as

x2 + y
,
xy + 1
where x and y are positive integers.

78 Determine all ordered pairs (m, n) of positive integers such that

n3 + 1
mn − 1
is an integer.

79 Determine all pairs of integers (a, b) such that

a2
2ab2 − b3 + 1
is a positive integer.

80 Find all pairs of positive integers m, n ≥ 3 for which there exist infinitely many positive integers
a such that
am + a − 1
an + a2 − 1
is itself an integer.

© 2019 AoPS Incorporated 8

AoPS Community PEN A Problems

81 Determine all triples of positive integers (a, m, n) such that am + 1 divides (a + 1)n .

82 Which integers can be represented as

(x + y + z)2
xyz
where x, y, and z are positive integers?
√
83 Find all n ∈ N such that b nc divides n.
√
84 Determine all n ∈ N for which - n is not the square of any integer, - b nc3 divides n2 .

85 Find all n ∈ N such that 2n−1 divides n!.

86 Find all positive integers (x, n) such that xn + 2n + 1 divides xn+1 + 2n+1 + 1.

87 Find all positive integers n such that 3n − 1 is divisible by 2n .

88 Find all positive integers n such that 9n − 1 is divisible by 7n .

89 Determine all pairs (a, b) of integers for which a2 + b2 + 3 is divisible by ab.

90 Determine all pairs (x, y) of positive integers with y|x2 + 1 and x2 |y 3 + 1.

91 Determine all pairs (a, b) of positive integers such that ab2 + b + 7 divides a2 b + a + b.

92 Let a and b be positive integers. When a2 + b2 is divided by a + b, the quotient is q and the
remainder is r. Find all pairs (a, b) such that q 2 + r = 1977.

93 Find the largest positive integer n such that n is divisible by all the positive integers less than
√
3
n.

94 Find all n ∈ N such that 3n − n is divisible by 17.

95 Suppose that a and b are natural numbers such that

r
b 2a − b
p=
4 2a + b
is a prime number. What is the maximum possible value of p?

96 Find all positive integers n that have exactly 16 positive integral divisors d1 , d2 · · · , d16 such
that 1 = d1 < d2 < · · · < d16 = n, d6 = 18, and d9 − d8 = 17.

© 2019 AoPS Incorporated 9

AoPS Community PEN A Problems

97 Suppose that n is a positive integer and let

d1 < d2 < d3 < d4

be the four smallest positive integer divisors of n. Find all integers n such that

n = d1 2 + d2 2 + d3 2 + d4 2 .

98 Let n be a positive integer with k ≥ 22 divisors 1 = d1 < d2 < · · · < dk = n, all different.
Determine all n such that
n 2
 
2 2
d7 + d10 = .
d22

99 Let n ≥ 2 be a positive integer, with divisors

1 = d1 < d2 < · · · < dk = n .

Prove that
d1 d2 + d2 d3 + · · · + dk−1 dk
is always less than n2 , and determine when it divides n2 .

100 Find all positive integers n such that n has exactly 6 positive divisors 1 < d1 < d2 < d3 < d4 <
n and 1 + n = 5(d1 + d2 + d3 + d4 ).

101 Find all composite numbers n having the property that each proper divisor d of n has n − 20 ≤
d ≤ n − 12.

102 Determine all three-digit numbers N having the property that N is divisible by 11, and N
11 is
equal to the sum of the squares of the digits of N.

103 When 44444444 is written in decimal notation, the sum of its digits is A. Let B be the sum of the
digits of A. Find the sum of the digits of B. (A and B are written in decimal notation.)

104 A wobbly number is a positive integer whose digits in base 10 are alternatively non-zero and
zero the units digit being non-zero. Determine all positive integers which do not divide any
wobbly number.

105 Find the smallest positive integer n such that - n has exactly 144 distinct positive divisors, -
there are ten consecutive integers among the positive divisors of n.

© 2019 AoPS Incorporated 10

AoPS Community PEN A Problems

106 Determine the least possible value of the natural number n such that n! ends in exactly 1987
zeros.

107 Find four positive integers, each not exceeding 70000 and each having more than 100 divisors.

108 For each integer n > 1, let p(n) denote the largest prime factor of n. Determine all triples
(x, y, z) of distinct positive integers satisfying - x, y, z are in arithmetic progression, - p(xyz) ≤
3.

109 Find all positive integers a and b such that

a2 + b b2 + a
and
b2 − a a2 − b
are both integers.

For each positive integer n, write the sum nm=1 1/m in the form pn /qn , where pn and qn are
P
110
relatively prime positive integers. Determine all n such that 5 does not divide qn .

111 Find all natural numbers n such that the number n(n + 1)(n + 2)(n + 3) has exactly three
different prime divisors.

112 Prove that there exist infinitely many pairs (a, b) of relatively prime positive integers such that

a2 − 5 b2 − 5
and
b a
are both positive integers.

113 Find all triples (l, m, n) of distinct positive integers satisfying

gcd(l, m)2 = l + m, gcd(m, n)2 = m + n, and gcd(n, l)2 = n + l.

114 What is the greatest common divisor of the set of numbers

{16n + 10n − 1 | n = 1, 2, · · · }?

115 Does there exist a 4-digit integer (in decimal form) such that no replacement of three of its
digits by any other three gives a multiple of 1992?

© 2019 AoPS Incorporated 11

AoPS Community PEN A Problems

116 What is the smallest positive integer that consists base 10 of each of the ten digits, each used
exactly once, and is divisible by each of the digits 2 through 9?

117 Find the smallest positive integer n such that

21989 | mn − 1

for all odd positive integers m > 1.

118 Determine the highest power of 1980 which divides

(1980n)!
.
(n!)1980

© 2019 AoPS Incorporated 12

Art of Problem Solving is an ACS WASC Accredited School.