Project Euler #134

259 Views Asked by At

The problem statement is here:

Consider the consecutive primes $p_{1}$ = 19 and $p_{2}$ = 23. It can be verified that $1219$ is the smallest number such that the last digits are formed by $p_{1}$ whilst also being divisible by $p_{2}$.

In fact, with the exception of $p_{1} = 3$ and $p_{2} = 5$, for every pair of consecutive primes, $p_{2} > p_{1}$, there exist values of n for which the last digits are formed by $p_{1}$ and n is divisible by $p_{2}$. Let $S$ be the smallest of these values of n.

Find $\sum S$ for each pair of consecutive primes with $5\leq p_1\leq 1000000$.

The original statement looks for a sum, but I'm just trying to find $S$. I read the solution online, but I don't understand it. Specifically, the solution says that the number that I'm trying to find has $D_{1} +1$ digits if $D_{1}$ is the number of digits of $p_{1}$

$n\equiv 0\pmod{p_{2}}$

$n\equiv p_{1}\pmod{D_{1}}$

Solving these obtained will apparently yield $S\pmod{D_{1}p_{2}}$, but I don't see why? Specifically how the the second was congruence obtained.

1

There are 1 best solutions below

0
On BEST ANSWER

The second congruence is incorrect; it should be $$n\equiv p_1\mod{10^{D_1}}.$$ The reason this congruence must hold is that it expresses the fact that $n$ ends with $p_1$: it says that considering the last $D_1$ digits of $n$ gives $p_1$, where $D_1$ is the number of decimal digits in $p_1$.

So it should be clear that solving this pair of congruences gives one possible $S$. I don't want to say too much more since the Project Euler problems are intended to be solved individually.