Let $t,x$ be positive integers and $q$ be any prime.
I was told that you can solve for $t^x \equiv 1 \pmod {q\#}$ by solving for each prime factor of $q\#$ and then setting $x$ to the least common multiple of the solution for each prime.
For example, for $t=13$ and $q=7$, we have:
- $13^1 \equiv 1 \pmod 2$
- $13^1 \equiv 1 \pmod 3$
- $13^4 \equiv 1 \pmod 5$
- $13^2 \equiv 1 \pmod 7$
So, since $4$ is the least common multiple, it follows that:
$$13^4 \equiv 1 \pmod {7\#}$$
Could someone explain why this is true? I checked the wikipedia article on modular arithmetic but didn't see any details on this property.
We know that $a^n-1|a^{k\cdot n}-1$ for every $k\geq 1$ .
Suppose that $p_i|t^{x_i}-1$ for $i=1,\cdots ,k$.
If $x$ denotes the least common multiple of the $x_i$ ,there exists a natural number $k_i$, with $x=k_i\cdot x_i$.
So, $t^{x_i}-1|t^x-1$ which means that also $p_i|t^{x}-1$ for every prime number $p_i$.
This leads us to a proof that $p_1\cdot p_2\cdots p_k|t^x-1$