MHB Proving the Existence of K for Prime P and 10^K Mod P = 1

[mathworker]

Prove or disprove for every prime P there is a K such that $$10^k=1\text{mod}P$$.
I arrived at this statement while proving something and can't find progress
here is the problem which may doesn't matter but if you wan't to find the origin [here]

 

[chisigma]

Re: prime divisors

Prove or disprove for every prime P there is a K such that $$10^k=1\text{mod}P$$.
I arrived at this statement while proving something and can't find progress

Of course the trivial cases k=0 and p=2 and p=5 are not allowed...

Kind regards$\chi$ $\sigma$

 

[mathworker]

Re: prime divisors

Of course the trivial cases k=0 and p=2 are not allowed...

Kind regards$\chi$ $\sigma$

yeah i am looking at n=5 to, as it is the only prime that divides 10

 

[chisigma]

Re: prime divisors

yeah i am looking at n=5 to, as it is the only prime that divides 10

By definition if n is prime, then n is the only prime deviding n, otherwise. if n isn't power of prime, there are at least two primes deviding n... Kind regards$\chi$ $\sigma$

 

[mathworker]

Re: prime divisors

By definition if n is prime, then n is the only prime deviding n, otherwise there are at least two primes deviding n... Kind regards$\chi$ $\sigma$

sorry,i mean any $$10^k$$(excluding '2')

 

[Nono713]

Re: prime divisors

Prove or disprove for every prime P there is a K such that $$10^k=1\text{mod}P$$.
I arrived at this statement while proving something and can't find progress
here is the problem which may doesn't matter but if you wan't to find the origin [here]

The problem is actually trivial with a little knowledge of information theory and reversibility (ergodic theory).

We will first state a little lemma:

Lemma 1: Let $f$ be a bijective function on a finite set, and let $\left ( u_n \right )_{n = 0}^\infty$ be a sequence such that:

$$u_{n + 1} = f(u_n) ~ ~ ~ \text{for some} ~ u_0$$

1. Because $f$ is defined on a finite set, $\left ( u_n \right )_{n = 0}^\infty$ must be periodic.

2. Because $f$ is bijective, $\left ( u_n \right )_{n = 0}^\infty$ must be periodic in $u_0$, that is, there exists a $k > 0$ such that $u_{k + n} = u_n$ for all integers $n \geq 0$.

This is an extremely powerful (and beautiful) lemma, and it is fairly easy to prove. I'll let you give it a shot, mathworker. The first fact should be easy enough, for the second one, here's a hint: the sequence is periodic, so $u_{-1}$ can be meaningfully defined. What does $f$ being bijective imply about $u_{-1}$? About $u_{-2}$? Keep going until you reach a contradiction!

Proof of Theorem: Let the function $f : \mathbb{Z} / p \mathbb{Z} \to \mathbb{Z} / p \mathbb{Z}$ be defined as $f(x) = 10x \mod{p}$.

This function has a finite domain/range, and is also bijective, because $\gcd{(10, p)} = 1$ as $p$ is prime.

Now define the sequence $u_0 = 1$, $u_{n + 1} = f(u_n)$. We see that $u_n = 10^n \mod p$.

Then by Lemma 1, there exists a $k > 0$ such that $u_k = u_0$. In other words, there exists a $k$ such that $10^k \equiv 1 \pmod{p}$, and the theorem is proved.​

$\blacksquare$

Note this generalizes to all bases greater than one. Indeed, the following is true:

For all primes $p$ and integers $b$ coprime to $p$, there exists a $k$ such that:

$$b^k \equiv 1 \pmod{p}$$

Here's a proof of the lemma if you are stuck:

Spoiler

Part 1: because $f$ is defined on a finite set, by the pigeonhole principle there exists a $k$ such that $u_k = u_m$ for $0 \leq m < k$ (in other words, the sequence eventually repeats itself). At that point the sequence will again produce $u_{m + 1}$, $u_{m + 2}$, and so on, therefore it has entered a cycle of period $k - m$.

Part 2: we showed previously that there exists a $k$ such that $u_k = u_m$ for $0 \leq m < k$. But since $f$ is bijective, this implies that $u_{k - 1} = u_{m - 1}$, $u_{k - 2} = u_{m - 2}$, and so on. Repeat the argument until you reach $u_{k - m} = u_0$, and as $k > m$ we have shown that the sequence $\left ( u_n \right )_{n = 0}^\infty$ has entered a cycle containing $u_0$, and the lemma is proved.

Granted this may be massive overkill, but I think you should learn the lemma anyway. It's extremely useful.

 

[mathworker]

Re: prime divisors

As,$$f$$ is defined on finite set , both $$u_n$$ and $$u_{n+1}$$ belongs to set,so for nth term in the set there exists another term in set which after finite number of strikes hit back to nth term.
What is the difference between
$$\left ( u_n \right )_{n = 1}^\infty$$ must be periodic
and
$$\left ( u_n \right )_{n = 1}^\infty$$ must be periodic in u0

 

[Nono713]

Re: prime divisors

As,$$f$$ is defined on finite set , both $$u_n$$ and $$u_(n+1)$$ belongs to set,so for nth term in the set there exists another term in set which after finite number of strikes hit back to nth term.
What is the difference between

Correct for the first part. For the second part, consider the two sequences:

$$\{ 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, \cdots \}$$

$$\{ 1, 2, 3, 4, 5, 4, 5, 4, 5, 4, 5, \cdots \}$$

The first one is periodic in $u_0$ - the second one isn't.

For reference, this is basically a special case of Poincaré's recurrence theorem, applied to a simple finite system. As there is no loss of information (energy in the original theorem) due to the reversibility of the map function $f$, the state ($u_n$) will eventually return to its original configuration ($u_0$) after a sufficient number of iterations :D

 

[mathworker]

Re: prime divisors

That's been a great help thanks for lemma and proof, can we extend this for all natural numbers?

 

[Nono713]

Re: prime divisors

That's been a great help thanks for lemma and proof, can we extend this for all natural numbers?

Do you mean the original statement? Yes, any base other than 10 will work as long as it is coprime with $p$ (see the end of my first post). In fact this can be used to prove a bunch of other such "there exists" statements, as long as you can find a bijective function $f$ that correctly describes the expression. In this case it was easy since $10^k$ can be expressed as iteratively multiplying by 10, so it lent itself quite well to this approach.

Formally, if you have a statement of the form:

There exists a $k > 0$ such that $g(k) = a$, and $g(0) = a$.

Then if there exists a bijective function $f$ such that $f_k(a) = g(k)$ (where $f_k$ denotes "iterate the function $f$, $k$ times on the input") for all $k \geq 0$, the statement is true.

This isn't an if and only if theorem, though. It's possible for the statement to be true even though no such $f$ exists, by pure coincidence. The lemma only says that it must be true if such an $f$ exists.​

 

[mathworker]

Re: prime divisors

Do you mean the original statement? Yes, any base other than 10 will work as long as it is coprime with $p$ (see the end of my first post). In fact this can be used to prove a bunch of other such "there exists" statements, as long as you can find a bijective function $f$ that correctly describes the expression. In this case it was easy since $10^k$ can be expressed as iteratively multiplying by 10, so it lent itself quite well to this approach.

Formally, if you have a statement of the form:
Then if there exists a bijective function $f$ such that $f_k(a) = g(k)$ (where $f_k$ denotes "iterate the function $f$, $k$ times on the input") for all $k \geq 0$, the statement is true.

This isn't an if and only if theorem, though. It's possible for the statement to be true even though no such $f$ exists, by pure coincidence. The lemma only says that it must be true if such an $f$ exists.​

i am actually talking 'bout $$10^k=1\text{mod}(N)$$

 

[Nono713]

Re: prime divisors

i am actually talking 'bout $$10^k=1\text{mod}(N)$$

If $\gcd{(10, N)} = 1$ then the statement holds :)

This is because our function $f$ then becomes:

$$f(x) = 10x \mod N$$

Which is bijective if and only if $10$ is invertible modulo $N$ ;)

 

[mathworker]

Re: prime divisors

If $\gcd{(10, N)} = 1$ then the statement holds :)

This is because our function $f$ then becomes:

$$f(x) = 10x \mod N$$

Which is bijective if and only if $10$ is invertible modulo $N$ ;)

If so,for every $$\text{gcd}(N_1,N_2)=1$$
so if we can find X for every N such that $$\text{gcd}(10^X-N,N)=1$$,
then there exists a k such that,
$$(10^X-N)^K=1\text{mod}(N)\rightarrow10^{(XK)}=1\text{mod}(N)$$
so it can be true for 'odd'N even though $$\text{gcd}(10,N)\cancel{=
}1$$ so can we find X ? i seems like we can
EDIT:NO,we can't how did i forgot even numbers,how about odd?

 

[Nono713]

Re: prime divisors

If so,for every $$\text{gcd}(N_1,N_2)=1$$
so if we can find X for every N such that $$\text{gcd}(10^X-N,N)=1$$,
then there exists a k such that,
$$(10^X-N)^K=1\text{mod}(N)\rightarrow10^{(XK)}=1\text{mod}(N)$$
so it can be true for N even though $$\text{gcd}(10,N)\cancel{=
}1$$ so can we find X ? i seems like we can

I am not sure - it's possible the statement cannot actually hold unless $10$ and $N$ are coprime, but I haven't thought of a proof yet.

By the way, if you wanted to actually find $k$ - one possible solution is $k = \varphi{(N)}$ (that's $k = p - 1$ if $p$ is prime), if $10$ and $N$ are coprime. This uses Euler's Theorem and also proves your statement in a more "number theoretical" fashion :) but that was the "easy" proof - I just wanted to introduce you to this different, more powerful approach to help you prove more difficult theorems in the future