Composites with Prime Repunit Property

A number consisting entirely of ones is called a repunit. We shall define $R(k)$ to be a repunit of length $k$; for example, $R(6) = 111111$.
Given that $n$ is a positive integer and $\gcd(n, 10) = 1$, it can be shown that there always exists a value, $k$, for which $R(k)$ is divisible by $n$, and let $A(n)$ be the least such value of $k$; for example, $A(7) = 6$ and $A(41) = 5$.
You are given that for all primes, $p \gt 5$, that $p – 1$ is divisible by $A(p)$. For example, when $p = 41$, $A(41) = 5$, and $40$ is divisible by $5$.
However, there are rare composite values for which this is also true; the first five examples being $91$, $259$, $451$, $481$, and $703$.
Find the sum of the first twenty-five composite values of $n$ for which $\gcd(n, 10) = 1$ and $n – 1$ is divisible by $A(n)$.

This problem might be a bit complex, due to its number theory content. To solve it, one needs to understand certain concepts such as the Euler’s totient function, and canonical representation of number.

In the question, we are asked to find the sum of the first twenty-five composite values of n for which $gcd(n, 10)=1$ and $n – 1$ is divisible by $A(n)$. The ‘number consisting entirely of ones’ aka repunit properties are applied.

However, to solve this problem, it is important to point out that the value of $A(n)$ for an integer $n$ such that $\gcd(n,10)=1$ is equivalent to the order of 10 modulo $n$. Hence, any number $n$ we seek must satisfy $ord_n(10) | n-1$.

Note that if $n$ is a prime number, then $ord_n(10) | \phi(n)=n-1$, where $\phi$ is Euler’s totient function. On the other hand, if $n$ is a composite number, $\phi(n) < n-1$, hence $ord_n(10) | \phi(n)$. We can now consider the canonical representation of $\phi(n)$, $\phi(n) = n \prod_{p | n}(1-\frac{1}{p})$. Since $ord_n(10) | \phi(n)$, it follows that there must be a prime $p$ such that $p | n$ and $p-1 | ord_n(10)$. If $q$ is a prime divisor of $n$ such that $q \neq p$, then as $ord_n(10) | \phi(n)$, it must hold that $ord_q(10) | \phi(q)=q-1$ divides $ord_n(10)$. Then $q-1 | p-1$, and since $p > q$, it follows that $q-1 \leq p-q$.

Taking all of these into account, we have the following approach:

1. List all primes $p < 10000$ such that $p = aq+1$ for some prime $q < p/2$ and $a \in \mathbb{N}$ 2. For each identified prime pairing $(p, q)$, we can generate potential numbers $n = pq^k$ for some $k \geq 1$ such that $\phi(n) | n-a$ 3. Test each candidate $n$ to see if $ord_n(10) | n-1$, and if yes, add $n$ to the answer. The computations are too large to carry out manually, and thus you will need to write a code or use a tool that assists with large computations. Please note, this problem is beyond the standard mathematical problems and requires a deep knowledge in number theory.

More Answers: