For every prime p consider all polynomials f(x) with integer coefficients from 1 to p and degree at most p−1, such that for all integers x the number f(2x)−f(x) is divisible by p.

Find the sum of all primes p<1000 such that the number of such polynomials is strictly greater than p⋅2^(p−2)

To solve this problem, we need to find the primes p that satisfy the given condition. We'll break down the problem into smaller steps:

Step 1: Understand the Condition
The condition states that for any prime p, we need to find polynomials f(x) with integer coefficients between 1 and p, and a degree at most p-1, such that for all integers x, the number f(2x) - f(x) is divisible by p.

Step 2: Polynomial Representation
We can represent the polynomial f(x) with integer coefficients as:
f(x) = a0 + a1*x + a2*x^2 + ... + an-1*x^(n-1),

where a0, a1, ..., an-1 are integers between 1 and p.

Step 3: Finding the Expression f(2x) - f(x)
Using the polynomial representation, we can calculate f(2x) - f(x) as follows:
f(2x) - f(x) = (a0 + a1*2x + a2*(2x)^2 + ... + an-1*(2x)^(n-1)) - (a0 + a1*x + a2*x^2 + ... + an-1*x^(n-1))
= (2^n)*(a0 + a1*x + a2*x^2/2 + ... + an-1*x^(n-1)/(2^(n-1))) - (a0 + a1*x + a2*x^2 + ... + an-1*x^(n-1))

From the above expression, we can see that f(2x) - f(x) will be divisible by p if and only if the entire term in the parentheses is divisible by p. Therefore, we can rewrite the condition as finding polynomials f(x) such that:
a0 + a1*x + a2*x^2/2 + ... + an-1*x^(n-1)/(2^(n-1)) ≡ 0 (mod p),

where ≡ denotes congruence modulo p.

Step 4: Simplifying the Condition
We can simplify the congruence condition by multiplying both sides by the common denominator (2^(n-1)). This gives us:
2^(n-1)*a0 + 2^(n-2)*a1*x + 2^(n-3)*a2*x^2 + ... + an-1*x^(n-1) ≡ 0 (mod p)

Notice that the coefficients of the polynomial on the left-hand side are no longer limited to integers between 1 and p. They can be any integers.

Step 5: Counting Possible Polynomials
Now, we want to count the number of possible polynomials that satisfy the congruence condition. Since each coefficient can be any integer, we have p choices for a0, a1, ..., an-1. Therefore, the total number of possible polynomials is p^n.

Step 6: Comparing with p*2^(p-2)
We are given that the number of polynomials must be strictly greater than p*2^(p-2). So, we need to find primes p for which p^n > p*2^(p-2).

Simplifying the inequality, we have:
p^(n-1) > 2^(p-2).

Step 7: Finding Suitable Primes
We need to find primes p that satisfy the inequality p^(n-1) > 2^(p-2). We'll iterate through primes less than 1000 and check if the given condition is satisfied.

Step 8: Summing Up
Finally, we'll sum up all the primes p that satisfy the condition p^(n-1) > 2^(p-2), and p < 1000.

By following these steps, we can find the sum of all such primes.