AIME Sprint · Number Theory AIME 冲刺 · 数论专题

Find the three-digit positive integer abc whose representation in base nine is bca_nine, where a, b, and c are (not necessarily distinct) digits.

Let N = 100a + 10b + c. Because N is a three-digit number, a ≥ 1; because a, b, c all appear as digits in base nine, each lies in {0,1,…,8}, and b ≥ 1 (it is the leading digit of the base-nine numeral). The base-nine expansion gives N = 81b + 9c + a. Hence

100a + 10b + c = 81b + 9c + a,   equivalently   99a = 71b + 8c.

Since 71b + 8c ≤ 71·8 + 8·8 = 632, we get 99a ≤ 632, so a ≤ 6.

Reduce 99a = 71b + 8c modulo 8. Since 99 ≡ 3 and 71 ≡ 7 (mod 8), this gives 3a ≡ 7b (mod 8), i.e. 3a ≡ −b (mod 8), so b ≡ −3a (mod 8). For a = 1,…,6 this forces b ≡ 5, 2, 7, 4, 1, 6 respectively, and every such residue lies in {1,…,8}, so b is determined. Substituting and solving for c = (99a − 71b)/8:

• a = 1, b = 5: c = (99 − 355)/8 < 0 — impossible;
• a = 2, b = 2: c = (198 − 142)/8 = 7   valid;
• a = 3, b = 7: c = (297 − 497)/8 < 0 — impossible;
• a = 4, b = 4: c = (396 − 284)/8 = 14 > 8 — not a digit;
• a = 5, b = 1: c = (495 − 71)/8 = 53 > 8 — not a digit;
• a = 6, b = 6: c = (594 − 426)/8 = 21 > 8 — not a digit.

The only solution is (a, b, c) = (2, 2, 7). Check: 227 in base nine is 2·81 + 7·9 + 2 = 162 + 63 + 2 = 227.

The sum of all positive integers m such that 13!m is a perfect square can be written as 2^a3^b5^c7^d11^e13^f, where a, b, c, d, e, and f are positive integers. Find a + b + c + d + e + f.

Factor 13! by counting prime powers: v₂ = 6+3+1 = 10, v₃ = 4+1 = 5, v₅ = 2, and v₇ = v₁₁ = v₁₃ = 1. So

13! = 2¹⁰·3⁵·5²·7·11·13 = 6 227 020 800.

If 13!/m is a perfect square then 13!/m is an integer, so m | 13!. Write m = 2^x3^y5^z7^p11^q13^r with 0 ≤ x ≤ 10, 0 ≤ y ≤ 5, 0 ≤ z ≤ 2, p, q, r ∈ {0,1}. Then

13!/m = 2^10−x3^5−y5^2−z7^1−p11^1−q13^1−r

is a perfect square exactly when all six exponents are even. This is six independent conditions:

• 10 − x even  ⟹  x ∈ {0, 2, 4, 6, 8, 10};
• 5 − y even  ⟹  y ∈ {1, 3, 5};
• 2 − z even  ⟹  z ∈ {0, 2};
• 1 − p, 1 − q, 1 − r even  ⟹  p = q = r = 1.

So there are 6·3·2 = 36 valid values of m, and their sum factorizes as a product of geometric-type sums (one factor per prime):

Σ m = (2⁰+2²+2⁴+2⁶+2⁸+2¹⁰)(3¹+3³+3⁵)(5⁰+5²)(7)(11)(13)
= (1365)(273)(26)(7)(11)(13).

Factor each piece: 1365 = 3·5·7·13, 273 = 3·7·13, 26 = 2·13. Multiplying and collecting exponents,

Σ m = 2¹3²5¹7³11¹13⁴ = 9 698 458 770.

Therefore a + b + c + d + e + f = 1 + 2 + 1 + 3 + 1 + 4 = 12.

Call a positive integer n extra-distinct if the remainders when n is divided by 2, 3, 4, 5, and 6 are distinct. Find the number of extra-distinct positive integers less than 1000.

Write r_k = n mod k. Note that r₂, r₄, r₆ all have the same parity (namely the parity of n). Since they must be pairwise distinct, each is forced once r₂ is known.

Case 1: n even. Then r₂ = 0. The values r₄ ∈ {0,2} and r₆ ∈ {0,2,4} must be even and distinct from 0 and from each other, so r₄ = 2 and r₆ = 4. Now r₃ ∈ {0,1,2} must avoid {0, 2, 4}, so r₃ = 1; and r₅ ∈ {0,…,4} must avoid {0, 2, 4, 1}, so r₅ = 3. So

n ≡ 0 (2), n ≡ 1 (3), n ≡ 2 (4), n ≡ 3 (5), n ≡ 4 (6).

The conditions mod 4 and mod 6 give n ≡ 10 (mod 12); combining with n ≡ 3 (mod 5) (moduli coprime) gives n ≡ 58 (mod 60).

Case 2: n odd. Then r₂ = 1, so r₄ = 3 and r₆ = 5. Conditions mod 4 and mod 6 give n ≡ 11 (mod 12), which forces r₃ = 11 mod 3 = 2 — and indeed 2 ∉ {1,3,5}, consistent. Then r₅ must avoid {1, 3, 5, 2}, so r₅ ∈ {0, 4}. Putting n = 11 + 12t, we have n ≡ (1 + 2t) (mod 5); this equals 0 for t ≡ 2 (mod 5) and equals 4 for t ≡ 4 (mod 5). Hence

n ≡ 11 + 24 = 35 (mod 60)  or  n ≡ 11 + 48 = 59 (mod 60).

So the extra-distinct integers are exactly those with n ≡ 35, 58, or 59 (mod 60). Counting those below 1000:

• n ≡ 35 (mod 60): 35 + 60t ≤ 999 gives t = 0,…,16 — that is 17 values;
• n ≡ 58 (mod 60): 58 + 60t ≤ 999 gives t = 0,…,15 — 16 values;
• n ≡ 59 (mod 60): 59 + 60t ≤ 999 gives t = 0,…,15 — 16 values.

Total 17 + 16 + 16 = 49.

Recall that a palindrome is a number that reads the same forward and backward. Find the greatest integer less than 1000 that is a palindrome both when written in base ten and when written in base eight, such as 292 = 444_eight.

Since 8⁴ = 4096 > 1000, every n < 1000 has at most four base-eight digits. Any number with at most three base-eight digits is less than 8³ = 512, so we first search among the four-digit base-eight palindromes

(d₁ d₂ d₂ d₁)₈ = 512d₁ + 64d₂ + 8d₂ + d₁ = 513d₁ + 72d₂,

with d₁ ∈ {1,…,7} and d₂ ∈ {0,…,7}. Requiring the value to be < 1000 rules out d₁ ≥ 2 (since 513·2 = 1026), so d₁ = 1 and 513 + 72d₂ < 1000 gives d₂ ≤ 6. The candidates are

513, 585, 657, 729, 801, 873, 945.

Checking which are base-ten palindromes: 513, 657, 729, 801, 873, 945 are not (their first and last digits differ), while 585 reads the same both ways. Its base-eight form is 1111_eight: indeed 1·512 + 1·64 + 1·8 + 1 = 585. Since 585 already exceeds 511, no number with fewer base-eight digits can beat it.

Find the number of positive integers n ≤ 600 whose value can be uniquely determined when the values of ⌊n/4⌋, ⌊n/5⌋, and ⌊n/6⌋ are given, where ⌊x⌋ denotes the greatest integer less than or equal to the real number x.

Fix n and set a = ⌊n/4⌋, b = ⌊n/5⌋, c = ⌊n/6⌋. Any m with the same triple satisfies 4a ≤ m ≤ 4a+3, 5b ≤ m ≤ 5b+4 and 6c ≤ m ≤ 6c+5, so the set of such m is the interval of integers [L, U] with

L = max(4a, 5b, 6c),    U = min(4a+3, 5b+4, 6c+5).

The triple determines n uniquely exactly when L = U = n.

Now ⌊(n+1)/k⌋ = ⌊n/k⌋ fails to hold precisely when k | (n+1), i.e. when n ≡ k−1 (mod k). Hence U = n ⟺ the triple of n+1 differs from that of n ⟺ n ≡ 3 (mod 4), or n ≡ 4 (mod 5), or n ≡ 5 (mod 6). Call this property A(n). Symmetrically, L = n ⟺ A(n−1) (this also handles n = 1 correctly, since A(0) is false: 0 ≢ 3, 0 ≢ 4, 0 ≢ 5). Therefore

n is uniquely determined  ⟺  A(n−1) and A(n).

A has period lcm(4,5,6) = 60. The residues A(r) with 0 ≤ r < 60 are the 28 values 3, 4, 5, 7, 9, 11, 14, 15, 17, 19, 23, 24, 27, 29, 31, 34, 35, 39, 41, 43, 44, 47, 49, 51, 53, 54, 55, 59. Among them, two consecutive residues r and r+1 are both in A exactly for r ≡ 3, 4, 14, 23, 34, 43, 53, 54 (mod 60) — 8 residues per period.

Finally, n ranges over 1 ≤ n ≤ 600, so r = n − 1 ranges over 600 consecutive integers, i.e. exactly 10 full periods of length 60. The count is 8 · 10 = 80.

(Check on the subtlety at the top end: for n = 600 we have (a,b,c) = (150,120,100), and m = 601, 602, 603 share that same triple, so 600 is not uniquely determined — matching A(600) being false.)

For each positive integer n let a_n be the least positive integer multiple of 23 such that a_n ≡ 1 (mod 2ⁿ). Find the number of positive integers n less than or equal to 1000 that satisfy a_n = a_n+1.

Since gcd(23, 2ⁿ) = 1, the congruence 23u ≡ 1 (mod 2ⁿ) has a unique solution u_n modulo 2ⁿ, and the least positive multiple of 23 congruent to 1 modulo 2ⁿ is a_n = 23u_n with 1 ≤ u_n < 2ⁿ. Hence 1 ≤ a_n < 23·2ⁿ, so writing

a_n = 1 + t_n2ⁿ

gives 1 ≤ t_n ≤ 22. Reducing a_n ≡ 0 (mod 23) yields 1 + t_n2ⁿ ≡ 0 (mod 23), that is

t_n ≡ −2⁻ⁿ (mod 23),

and t_n is the unique integer in [1,22] in that class.

Now a_n = a_n+1 ⟺ 2ⁿ⁺¹ divides a_n − 1 = t_n2ⁿ ⟺ t_n is even. Indeed, if t_n is even then a_n ≡ 1 (mod 2ⁿ⁺¹) and a_n is a multiple of 23, so a_n+1 ≤ a_n; conversely a_n+1 ≡ 1 (mod 2ⁿ⁺¹) implies a_n+1 ≡ 1 (mod 2ⁿ), so a_n+1 is an admissible candidate for a_n and a_n ≤ a_n+1.

Since 2¹¹ = 2048 = 89·23 + 1 ≡ 1 (mod 23), the value of 2⁻ⁿ modulo 23 depends only on m = n mod 11. Listing 2^e mod 23 for e = 0,…,10:

1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12.

With e = (11 − m) mod 11 we get t_n = 23 − (2^e mod 23), and t_n is even ⟺ 2^e mod 23 is odd. From the list, the odd entries occur at e = 0 (value 1), e = 5 (value 9), e = 7 (value 13) and e = 8 (value 3), corresponding to m = 0, 6, 4, 3 respectively. Hence

a_n = a_n+1  ⟺  n ≡ 0, 3, 4, or 6 (mod 11).

Finally 1000 = 11·90 + 10, so among 1 ≤ n ≤ 1000 there are 90 complete blocks of 11 residues (contributing 4 each) plus the tail residues 1,…,10, of which 3, 4, 6 qualify. The count is 90·4 + 3 = 363.

Let p be the least prime number for which there exists a positive integer n such that n⁴ + 1 is divisible by p². Find the least positive integer m such that m⁴ + 1 is divisible by p².

Step 1: find p. Suppose an odd prime p divides n⁴ + 1. Then n⁴ ≡ −1 (mod p), so n⁸ ≡ 1 but n⁴ ≢ 1 (mod p); hence ord_p(n) = 8, and since the order divides p − 1 we get 8 | p − 1, i.e. p ≡ 1 (mod 8). For p = 2: n⁴ + 1 ≡ 0 (mod 2) forces n odd, and every odd n has n⁴ ≡ 1 (mod 16), so n⁴ + 1 ≡ 2 (mod 16) is never divisible by 4. So p ≡ 1 (mod 8), and the smallest such prime is 17, which works because 2⁴ + 1 = 17.

Step 2: solve n⁴ + 1 ≡ 0 (mod 289). Modulo 17, the solutions are the elements of order 8 in (Z/17)^×, namely 2, 2³ = 8, 2⁵ = 32 ≡ 15, 2⁷ = 128 ≡ 9. So n ≡ 2, 8, 9, 15 (mod 17). Since f(n) = n⁴ + 1 has f′(n) = 4n³ ≢ 0 (mod 17) for these n, each solution lifts to a unique solution modulo 289. Write n = r + 17t; then f(n) ≡ f(r) + 17t·f′(r) (mod 289), so t is determined by f(r)/17 + t·f′(r) ≡ 0 (mod 17).

Using 8⁻¹ ≡ 15 and 9⁻¹ ≡ 2 and 15⁻¹ ≡ 8 (mod 17):

• r = 2: f(2) = 17, f′(2) = 32 ≡ 15, so 1 + 15t ≡ 0 ⟹ t ≡ −8 ≡ 9 ⟹ n ≡ 2 + 153 = 155;
• r = 8: f(8) = 4097 = 17·241, f′(8) = 2048 ≡ 8, so 241 + 2048t ≡ 3 + 8t ≡ 0 ⟹ 8t ≡ 14 ⟹ t ≡ 14·15 = 210 ≡ 6 ⟹ n ≡ 8 + 102 = 110;
• r = 9: f(9) = 6562 = 17·386, f′(9) = 2916 ≡ 9, so 386 + 2916t ≡ 12 + 9t ≡ 0 ⟹ 9t ≡ 5 ⟹ t ≡ 5·2 = 10 ⟹ n ≡ 9 + 170 = 179;
• r = 15: f(15) = 50626 = 17·2978, f′(15) = 13500 ≡ 2, so 2978 + 13500t ≡ 3 + 2t ≡ 0 ⟹ 2t ≡ 14 ⟹ t ≡ 7 ⟹ n ≡ 15 + 119 = 134.

The solutions modulo 289 are 110, 134, 155, 179, and the least positive one is 110. (Check: 110⁴ + 1 = 146 410 001 = 289 · 506 609.)

Let b ≥ 2 be an integer. Call a positive integer n b-eautiful if it has exactly two digits when expressed in base b and these two digits sum to √n. For example, 81 is 13-eautiful because 81 = 63₁₃ and 6 + 3 = √81. Find the least integer b ≥ 2 for which there are more than ten b-eautiful integers.

If n has exactly two base-b digits and they sum to √n, write n = b d₁ + d₀ with 1 ≤ d₁ ≤ b−1, 0 ≤ d₀ ≤ b−1, and put s = √n, so that d₁ + d₀ = s and n = s². Then d₁ = s − d₀ and

s² = b(s − d₀) + d₀ = bs − d₀(b−1)  ⟹  d₀(b−1) = s(b − s).

Since b ≡ 1 (mod b−1), we have b − s ≡ 1 − s (mod b−1), so d₀ = s(b−s)/(b−1) is an integer iff (b−1) | s(s−1). Put k = b − 1 and

h = s(s−1)/k,    d₁ = s − d₀ = s − [s(b−s)/k] = s − [s(k+1−s)/k] = s − [s − s(s−1)/k] = h,    d₀ = s − h.

So the conditions become: k | s(s−1); s(s−1) ≤ k² (from d₁ ≤ b−1 = k); 1 ≤ h = s(s−1)/k ≤ k; 0 ≤ s − h ≤ k; and s² = n ≥ b = k+1 (so s ≥ √(k+1)); and s ≤ k (since s² = n < b², as n has only two base-b digits). Every s with these properties gives exactly one b-eautiful n = s², and conversely.

Because gcd(s, s−1) = 1, the condition k | s(s−1) means k = k₁k₂ with k₁ | s, k₂ | s−1, gcd(k₁,k₂) = 1 — a unique factorization for each s. So each divisor pair of k produces at most one candidate s, found by solving s ≡ 0 (mod k₁), s ≡ 1 (mod k₂).

Take k = 210 = 2·3·5·7. Since k is squarefree, every divisor k₁ gives a coprime pair (k₁, k₂ = 210/k₁), and the corresponding s is the unique residue mod 210 in [1, 210]; the bound s(s−1) ≤ k² = 44100 is automatic for s ≤ 210, and we need s ≥ √211 ≈ 14.53. Enumerating the 16 divisors k₁:

k1	k2	s	k1	k2	s
1	210	1 — too small	21	10	21 ✓
2	105	106 ✓	30	7	120 ✓
3	70	141 ✓	35	6	175 ✓
5	42	85 ✓	42	5	126 ✓
6	35	36 ✓	70	3	70 ✓
7	30	91 ✓	105	2	105 ✓
10	21	190 ✓	210	1	210 ✓
14	15	196 ✓	15	14	15 ✓

That is 15 admissible values of s, hence 15 b-eautiful integers for b = 211 — more than ten. Applying the same criterion to every 2 ≤ b ≤ 210 gives at most 10 (the counts near the top are 7 for b = 205 and 3 for b = 206,…,210; the largest count below 211 is 7). Hence the least such b is 211.

Let ω ≠ 1 be a 13th root of unity. Find the remainder when ∏_k=0¹² (2 − 2ω^k + ω^2k) is divided by 1000.

Let f(x) = x² − 2x + 2 = (x − α)(x − β), where α = 1 + i and β = 1 − i are its two roots; note αβ = 2.

The 13th roots of unity are the roots of x¹³ − 1, so for every y we have ∏_k=0¹² (y − ω^k) = y¹³ − 1. Applying this with y = α and y = β and reversing the sign inside each of the 13 factors,

∏_k=0¹² (ω^k − α) = −(α¹³ − 1) = 1 − α¹³,    ∏_k=0¹² (ω^k − β) = 1 − β¹³.

Therefore the required product equals

∏_k=0¹² f(ω^k) = (1 − α¹³)(1 − β¹³) = 1 − (α¹³ + β¹³) + (αβ)¹³.

Now (αβ)¹³ = 2¹³ = 8192. For the other term, α² = 2i, α⁴ = (2i)² = −4 and α⁸ = 16, so

α¹³ = α⁸·α⁴·α = 16 · (−4) · (1 + i) = −64 − 64i,

and since β is the complex conjugate of α, β¹³ = −64 + 64i. Hence α¹³ + β¹³ = −128 and

∏_k=0¹² f(ω^k) = 1 + 128 + 8192 = 8321.

The remainder of 8321 upon division by 1000 is 321.

Let N be the greatest four-digit positive integer with the property that whenever one of its digits is changed to 1, the resulting number is divisible by 7. Let Q and R be the quotient and remainder, respectively, when N is divided by 1000. Find Q + R.

Write N = 1000a + 100b + 10c + d with a ∈ {1,…,9} and b, c, d ∈ {0,…,9}. Modulo 7 we have 1000 ≡ 6 ≡ −1, 100 ≡ 2 and 10 ≡ 3. Changing the first, second, third and fourth digit to 1 therefore gives the four conditions

(i) −1 + 2b + 3c + d ≡ 0,
(ii) −a + 2 + 3c + d ≡ 0,
(iii) −a + 2b + 3 + d ≡ 0,
(iv) −a + 2b + 3c + 1 ≡ 0   (all mod 7).

Subtracting (ii), (iii), (iv) from (i) in turn isolates the variables:

(i) − (ii): 2b ≡ 3 − a,    (i) − (iii): 3c ≡ 4 − a,    (i) − (iv): d ≡ 2 − a.

These are consistent only if (ii) also holds: substituting 3c ≡ 4 − a and d ≡ 2 − a into (ii) gives (4 − a) + (2 − a) ≡ a − 2 (mod 7), i.e. 8 ≡ 3a (mod 7). Since 3⁻¹ ≡ 5 (mod 7), a ≡ 40 ≡ 5 (mod 7), so a = 5.

Then d ≡ 2 − 5 ≡ 4 (mod 7), so d = 4 (the only value in 0,…,9); 2b ≡ 3 − 5 = −2 ≡ 5 (mod 7) with 2⁻¹ ≡ 4 gives b ≡ 20 ≡ 6 (mod 7), so b = 6; and 3c ≡ 4 − 5 = −1 ≡ 6 (mod 7) gives c ≡ 30 ≡ 2 (mod 7), so c ∈ {2, 9}.

Hence N ∈ {5624, 5694}, and the greatest is N = 5694. Check the four numbers obtained by changing a digit to 1: 1694 = 7·242, 5194 = 7·742, 5614 = 7·802, 5691 = 7·813 — all are divisible by 7.

Finally 5694 = 1000·5 + 694, so Q = 5 and R = 694, giving Q + R = 699.