MHB Appending a number to itself n times and finding modulo m

[Acquirer]

A number(p) is given. now p is appended to itself n times(n can be
as large as 10^10). I need to find the number thus formed modulo m.
Let the number be 12 and n be 4.
so number thus formed is 12121212. let us find this number modulo 11
then the ans is 4.

On observing the pattern it is clear that the modulo value starts repeating for some value of n.
let p=12 and m=7,
for n=1, mod= 5
for n=2,mod= 1
for n=3,mod=0
for n=4 onwards the same mod i.e. 5,1,0 starts repeating.but the problem is for many values of p and m the repitition starts after a large value of n thus making it difficult to calculate.
So, there should be an easier method for this maybe some more reliable pattern or formula. Pls help.

 

[I like Serena]

A number(p) is given. now p is appended to itself n times(n can be
as large as 10^10). I need to find the number thus formed modulo m.
Let the number be 12 and n be 4.
so number thus formed is 12121212. let us find this number modulo 11
then the ans is 4.

On observing the pattern it is clear that the modulo value starts repeating for some value of n.
let p=12 and m=7,
for n=1, mod= 5
for n=2,mod= 1
for n=3,mod=0
for n=4 onwards the same mod i.e. 5,1,0 starts repeating.but the problem is for many values of p and m the repitition starts after a large value of n thus making it difficult to calculate.
So, there should be an easier method for this maybe some more reliable pattern or formula. Pls help.

Hi Acquirer! Welcome to MHB! ;)

Let $p=12$ and $m=7$.
Let $P_n$ be the number with $p$ appended $n$ times to itself.

Then $P_1 = p = 12$ and:
$$P_2 \equiv P_1 \cdot 100 + p \equiv (P_1 \bmod 7) \cdot (100 \bmod 7) + (p \bmod 7)
\equiv (p \bmod 7)\cdot 2 + (p \bmod 7) \equiv 3(p \bmod 7) \equiv 1 \\
P_3 \equiv P_2 \cdot 100 + p \equiv (P_2 \bmod 7) \cdot 2 + (p \bmod 7)
\equiv 3(p \bmod 7)\cdot 2 + (p \bmod 7) \equiv 7(p \bmod 7) \equiv 0
$$

We see the pattern that the modulo number seems to be of the form $k(p \bmod m) \mod m$.
This is certainly true for $n=1$ with $k_1=1$.
So let's assume that $P_n \mod m = k_n \cdot p \mod m$.
And let $d$ be the number of digits of $p$.
Then:
$$P_{n+1} \equiv P_n \cdot 10^d + p \equiv (k_n \cdot p \bmod m) (10^d \bmod m) + (p \bmod m)
\equiv (k_n(10^d \bmod m)+1)(p \bmod m)
$$

So indeed, we have (by proof of induction):
$$P_n = k_n \cdot p \mod m$$
with $k_1=1$ and $k_{n+1} = (k_n(10^d \bmod m)+1) \bmod m$. (Thinking)

 

[I like Serena]

Let $t=10^d \bmod m$, then:
$$k_{n+1} = (k_n\cdot t+1) \bmod m$$
So:
$$k_1=1,\quad k_2=t+1 \bmod m,\quad k_3=t^2+t+1 \bmod m,\quad ...$$
This is a so called geometric series. When we apply the formula to sum a geometric series, we get:
$$k_n = \frac{t^n - 1}{t-1} \bmod m$$

Let's go back to the example with $p=12, m=7, d=2, t=100 \bmod 7 = 2$.
We have:
$$P_n \bmod 7 = k_n\cdot 12 \bmod 7 = \frac{2^n - 1}{2-1} \cdot 5 \bmod 7
= 5(2^{3q+r} - 1) \bmod 7 = 5(8^q\cdot 2^r - 1) \bmod 7
= 5(1^q\cdot 2^r - 1) \bmod 7
= 5(2^r - 1) \bmod 7
$$
where $q$ and $r$ are such that $n=3q+r$ with $r=0,1,2$.

So:
$$P_n \bmod 7=0,1,5$$
when $n$ is a multiple of 3 plus respectively 0, 1, or 2.

 

[I like Serena]

To find $(t-1)^{-1} \bmod m$, we're looking for a number $x$ such that $(t-1)x \equiv 1 \pmod m$.
As an example, suppose we have $t=3$ and $m=7$.
Then
$$(3-1)\cdot 4 \bmod 7 = 1$$
So:
$$(3-1)^{-1} \equiv 4 \pmod 7$$
To find it in general, we will need to apply the Euclidean algorithm.When I wrote $n=3q+r$, I meant that we should write $n$ as a multiple of $3$ plus a remainder $r < 3$.
The number $q$ is the quotient $q=\left\lfloor{\frac n 3}\right\rfloor$.
That's because we can simplify $2^3 \equiv 8 \equiv 1 \pmod 7$.

 

[Acquirer]

But the value of x exists only when t-1 and m are relatively co-prime i.e. gcd(t-1,m)=1. However the question may ask for some values where t-1 and m are not co-prime. in that case we need to look for some other method to do the same...

 

[I like Serena]

But the value of x exists only when t-1 and m are relatively co-prime i.e. gcd(t-1,m)=1. However the question may ask for some values where t-1 and m are not co-prime. in that case we need to look for some other method to do the same...

True.

Well... let again $P_n$ be the number consisting of $n$ times $p$ appended to itself, let $d$ be the number of digits of $p$, and let $t = 10^d \bmod m$.

Then we're looking for $P_n \bmod m = \frac{t^n - 1}{t-1}\cdot p \bmod m$.
That is, the remainder $r$ when we divide by $m$.
We can write it as:
$$\frac{t^n - 1}{t-1}\cdot p = qm + r$$
That is, we divide by $m$ leaving us the quotient $q$ and the remainder $r < m$, and we're looking for that remainder $r$.
It follows that:
$$(t^n - 1)\cdot p = qm(t-1) + r(t-1)$$
So:
$$(t^n - 1)\cdot p \mod m(t-1) = r(t-1)$$
Thus:
$$P_n \bmod m = r = \frac{1}{t-1}\Big((t^n - 1)\cdot p \mod m(t-1)\Big)$$

 

[Acquirer]

Thank You very much for making the solution so clear.
Finally I will clarify two edge cases which one need to take care of.
the first is when t=1, then instead of a G.P. an A.P will be formed so tn in that case will be simply n.
the second is when t=0, then Pn mod m will be simply p mod m.
Thank you again.