$n_{1},\ldots ,n_{k}, a$ are integers that satisfies the above conditions A)For every $i\neq j$, $(n_{i}, n_{j})=1$ B)For every $i, a^{n_{i}}\equiv 1 (mod n_{i})$ C)For every $i, X^{a-1}\equiv 0(mod n_{i})$. Prove that $a^{x}\equiv 1(mod x)$ congruence has at least $2^{k+1}-2$ solutions. ($x>1$)
Problem
Source:
Tags: number theory unsolved, number theory
28.10.2006 14:44
Hehe, two problems from turkish MO of same "type".
29.10.2006 16:28
i cant understand what is the question of the same type on the second round of 1993
30.10.2006 17:23
http://www.mathlinks.ro/Forum/viewtopic.php?t=112708 not same year, still funny
18.09.2014 05:24
The problem is not quite clear. Can some one from Turkey clarify this problem, especially condition C).
08.12.2017 17:09
The condition $c)$ is problematic above. For the sake of convenience, I'll rewrite the problem. Given positive integers $n_1,n_2,\dots,n_k,a$, satisfying: $\bullet$ $(n_i,n_j)=1$ if $i\neq j$, $\bullet$ $a^{n_i} \equiv 1 \pmod{n_i}$, for every $i$, $\bullet$ $n_i \nmid a-1$, show that the total number of integers $x\geq 2$, enjoying $a^x \equiv 1 \pmod{x}$ is at least $2^{k+1}-2$. I will post my solution later, unless someone else already posts till then.
09.12.2017 04:04
Enough waiting time ... Here is the proof, that I've promised to post. We begin by a few observations. First, notice that, $a$ is coprime with any $n_i$. Next, Claim None of the $n_i$'s are prime numbers. Proof Assume that $n_i$ is prime for some $i$. By Fermat's little theorem, we have $a^{n_i-1}\equiv 1 \pmod{n_i}$. Combining this with the second item above, gives us $n_i \mid a-1$, contradicting with the preamble.$\square$ The next claim gives us a way to generate such $x$'s. Claim Let $I$ be a non-empty subset of $\{1,2,\dots,k\}$. Define, $$ x_I \triangleq \prod_{i\in I}n_i. $$Then, $a^{x_I}\equiv 1 \pmod{x_I}$. Hence, we have shown the existence of at least $2^{k}-1$ such numbers. Proof First, notice that $a^{n_i}\equiv 1 \pmod{n_i}$ gives us, $a^{x_I}\equiv 1 \pmod{n_i}$, for every $i\in I$. Since $n_i$'s are coprime, we also have, $$ a^{x_I}\equiv 1 \pmod{x_I}. $$ Next, we will show the existence of a second collection, in a way, analogous to $\{n_1,n_2,\dots,n_k\}$, and therefore will conclude the proof. Claim For every $i$, let $p_i$ be the smallest prime divisor of $n_i$. Then, the following holds: $\bullet$ $n_i>p_i$ for every $i$. $\bullet$ $\{p_i:i=1,2,\dots,k\}$ consists of $k$-distinct primes. $\bullet$ $a \equiv 1 \pmod{p_i}$. Hence, $a^{p_i} \equiv 1\pmod{p_i}$. Noticing that this collection satisfies $a^{p_i}\equiv 1 \pmod{p_i}$ for every $i$, we can generate $2^{k}-1$ other such numbers via first taking a non-empty subset $I$ of $\{1,2,\dots,k\}$, and then, letting $y_I = \prod_{i\in I}p_i$. Since $n_i>p_i$ for every $i$, and $n_i$'s are coprime, this will generate $2^k-1$ other numbers, enjoying the desired property, and therefore establishing the proof. Proof For each $n_i$, we have already shown that $n_i$ cannot be a prime number, and therefore, $n_i>p_i$. Also, since $n_i$'s are coprime, for any $i\neq j$, the set of prime divisors of $n_i$ and the set of prime divisors of $n_j$ are disjoint, hence, $p_i$'s are all distinct. It remains to prove the last item. For this, note that by Fermat's theorem, we have $a^{p_i-1}\equiv 1 \pmod{p_i}$. Now, since $a^{n_i}\equiv 1 \pmod{p_i}$, we have, $$ a^{(n_i,p_i-1)}\equiv 1 \pmod{p_i} \implies a\equiv 1\pmod{p_i}, $$where the last assertion holds due to the fact that since $p_i$ is the smallest prime divisor of $n_i$, none of the prime divisors of $p_i-1$ can divide $n_i$, hence they are coprime.