Finding the Remainder of a Number Composed of 9s Divided by 13

In this article, we explore a mathematical problem involving number theory and modular arithmetic. Specifically, we seek to find the remainder when a large number composed entirely of digit 9s, written 99 times, is divided by 13. This problem involves concepts such as geometric series and Fermat's Little Theorem. We'll walk through the detailed steps and calculations to reach the final answer.

Understanding the Problem

The problem at hand involves the number N, which is formed by repeating the digit 9, ninety-nine times. Mathematically, this can be represented as:

N 999999...999 (99 nines)

Representation and Simplification

To simplify this problem, we start by expressing N in a more compact form:

N 9 times 10^{98} 9 times 10^{97} 9 times 10^{96} ... 9 times 10^0

This is a geometric series with the first term a 9, the common ratio r 10, and the number of terms n 99. The sum S of a geometric series can be calculated as follows:

S a frac{r^n - 1}{r - 1}

Substituting a 9, r 10, and n 99:

N 9 times frac{10^{99} - 1}{9} 10^{99} - 1

Modular Arithmetic and Fermat’s Little Theorem

To find the remainder of N when divided by 13, we need to compute:

N mod 13 (10^{99} - 1) mod 13

First, we determine 10^{99} mod 13. According to Fermat's Little Theorem, if p is a prime number and a is not divisible by p, then:

a^{p-1} equiv 1 mod p

Here, p 13 and a 10, so:

10^{12} equiv 1 mod 13

Next, we find the remainder when 99 is divided by 12:

99 div 12 8 text{ remainder } 3

Thus, 99 mod 12 3. Using this, we can simplify 10^{99} mod 13 as:

10^{99} mod 13 equiv 10^3 mod 13

We then calculate 10^3 mod 13:

10^1 equiv 10 mod 13

10^2 equiv 100 mod 13 equiv 9 mod 13 (since 100 - 7 times 13 9)

10^3 equiv 10 times 9 mod 13 equiv 90 mod 13 equiv 12 mod 13 (since 90 - 6 times 13 12)

Substituting this back, we get:

N mod 13 10^{99} - 1 mod 13 equiv 12 - 1 mod 13 equiv 11 mod 13

Therefore, the remainder when the number N is divided by 13 is 11.

Brute Force Solution

We can also verify this using a brute force method with a programming language like J. Here is how the solution would look in J code:

This calculates the remainder of the 99-digit number composed of 9s when divided by 13 and confirms the answer is 11.

Alternative Method

Alternatively, if we take a 6-digit number consisting entirely of 9s, which is 999999, and find the remainder when divided by 13, we get a remainder of 0. Multiplying this 6-digit number by 96 (since 6 times 16 96), we find that 96 times 999999, when divided by 13, still gives a remainder of 0. However, considering the last three digits, 999 div 13 gives a quotient of 76 and a remainder of 11.

Thus, the remainder of N, composed of 99 nines, when divided by 13 is boxed{11}.