Prime Divisors Positive Difference

First observe that if n is congruent to 1 mod p (for some prime divisor p of x), x is then congruent to 101 mod p and thus p = 101.

Now assume that n is not congruent to 1 mod p. Observe that since x is congruent to 0 mod p, we have:

x = n^100 + n^ 99 + .... + 1 congruent to 0 mod p

(n-1)(x) = (n^101-1) is congruent to 0 mod p

n^101 is congruent to 1 mod p

Let 101 = k(p-1) + m, for a non negative integer k and 0 <= m < p-1.

Note that n^(m) is congruent to 1 mod p by Fermat's little theorem

Note that m is not 1, as that would imply n is congruent to 1 mod p. Also, since we have considered the case of p = 101, we can ignore it, and thus m is not 0 either.

Lemma: if m and p-1 are coprime, we can express every integer from 1 to p-1 in the form am + b(p-1) where a and b are integers.

Proof: Consider m, 2m, 3m ....(p-1)m. These are all distinct modulo (p-1) and must thus form the residue set (1,2,3...p-1) modulo p-1

As a result of this lemma, if m and p-1 are coprime we can express n,n^2,n^3...,n^(p-1) as the product of powers of n^m and n^(p-1). All of them will be congruent to 1 modulo p-1, a contradiction.

Thus m and p-1 have a common prime factor q.

101 = k(p-1) + m is a multiple of q and thus q is 101, thus p-1 is a multiple of 101

Observe that 102,203,304,405,506 are all not prime. Also, 607 and 809 are primes. Note that p = (101)c + 1 can only be prime if c is even, implying the minimum gap of primes of this form is 202.

Thus the valid 'candidates' for prime divisors of x are 101, and all primes congruent to 1 mod 202.

Since the gap between 101 and 607 (the smallest prime congruent to 1 mod 202) is 506, pd(x) must be at least 202. We now only need to show that there exists n s.t. x is divisible by 607 and 809 to prove that pd(x) can be 202.

Let r = s = 2 (any r and s s.t. r^6 and s^8 are not congruent to 1 mod 607 and 809 will work, but 2 is the easiest)

(r^6)^101 is congruent to 1 mod 607, (s^8)^101 is congruent to 1 mod 809

and clearly, r^6 and s^8 are not congruent to 1 mod 607 and 809.

Observe that if n is congruent to r^6 mod 607 (we can apply an identical argument for s^8 and 809)

x = 1 + n + n^2 + ...+ n^100 (n-1)x = n^101 - 1 which is a multiple of 607.

Since (n-1) is not a multiple of 607, x must be a multiple of 607.

Because 607 and 809 are coprime, by the Chinese Remainder theorem we can pick n s.t. n is congruent to r^6 mod 607 and is congruent to s^8 mod 809. The resultant x will be a multiple of both 607 and 809, completing the proof

Suppose that there is a prime $p \mid n^{100} + ... + 1$ , so $p \mid \frac{n^{101}-1}{n-1}$ .

Suppose $p \not\equiv 1 \mod 101$ . Since 101 is prime, the function $a \mapsto a^{101}$ must be injective. In particular, $a \equiv 1 \mod p$ . However, by the Lifting the Exponent lemma , p divides $n^{101} - 1$ as many times as it divides $n - 1$ , unless of course $p = 101$ . But, as we'll see, this won't matter.

If $p \equiv 1 \mod 101$ , then by the existence of a primitive root, there exists a residue mod p such that $p \mid n^{101} - 1$ but $p \nmid n - 1$ . Since the smallest such primes are 607 and 809, then we don't need to worry about 101 having a smaller difference somewhere.

We know therefore that any difference is divisible by 101, and since both primes must be odd, 202 is the smallest possible.

Use Chinese remainder to show that there's an n which works for both 607 and 809, and we're done.

Write $x=\phi_{101}(n)$ (that is, the 101-th cyclotomic polynomial). Let $p$ be a prime divisor of $x$ . First, $p\neq2$ . Note then that $p\nmid n$ , so there exist a $k=\text {ord}_p (n)$ such that $n^k\equiv1\pmod p$ ; but we also have that $0\equiv x (n-1)\equiv n^{101}-1 \pmod p$ , so $k\mid101$ ; but 101 is prime, so we can have only $k=1, 101$ . If $k=1$ , then $n\equiv1\pmod p$ so we can apply LTE lemma and get $v_p (n^{101}-1)=v_p (n-1)+v_p (101)$ , so $v_p (x)=v_p (n^{101}-1)-v_p (n-1)=v_p (101)$ . So one possible divisor is $ p=101 $. If $k=101$ , we have th well known divisibility $\text {ord}_p (a)\mid p-1$ which tells us that $p=101k+1$ . From the list, the first few primes are 607, 809, etc... Now, $607-101> 809-607$ , so since we want the smallest $dp (x)$ , we don't use 101. So $dp (x)=101k+1-(101h+1)=101 (k-h)$ ; if the difference was 101, then k and h had different parity, so one of $101k+1$ and $101h+1$ would be even, but all primes are odd. So the difference is at least 202; indeed, we see that $7^{101}-1$ is a multiple of 607 and 809, so this difference can be attained and so $\boxed {202}$ is the answer.

Suppose that there is a prime $p$ such that $p \mid n^{100}+n^{99}+----+1$ . So, $p \mid(\frac{n^{101}-1}{n-1})$ Suppose, $p\equiv1\pmod{101}$ Since, $101$ is a prime, the function $a\rightarrow a^{101}$ must be injective. In particulr, $a\equiv1\pmod{p}$ . However by the Lifting The Exponent Lemma , $p\mid n^{101}-1$ as many times at it divides $n-1$ , unless of course $p=101$ . But, as we'll see, this won't matter. If $p \equiv 1\pmod101$ then by existence of a primitive root, there exists a resudue modulo $p$ such that $p\mid n^{101}-1$ but $p\nmid n-1$ Since, the smallest such primes are $607$ and $809$ , then we don't need to worry about $101$ having a smaller difference somewhere. We know, therefore that any difference is divisible by $101$ , and since both the primes must be odd, $\boxed{202}$ is the smallest possible. Use Chinese Remainder Theorem to show there exists an $n$ which works for both $607$ and $809$ .

We need to find the closest pair of 2 primes p1 and p2 such that both pi and p2 divide the no. x given for some positive integer n. We find the first few primes to be 607, 809, 1213, 3637,4243..... So the lowest difference or the pd would be 809-607=202 and this happens when n=7.

therefore pd(x)>=202(it can't be 101), 607 and 809 are both primes so it's possible