Note : This problem has no specific source .

Let $n$ be a composite number of the form :

$n=p^{a_1}_1\cdot p^{a_2}_2 \ldots p^{a_k}_k $ , where $p_1,p_2 , \ldots p_k$ are distinct primes and $a_1,a_2,\ldots a_k >0$ ; $k>1$ .

Is it true that :

If $ ~p^{n-1}_i \equiv r_i \pmod n ~\text{and}~ 0 \leq r_i \leq n-1 ~\text{then}~ r_i >1$

My attempt :

a) suppose $r_i=1$

According to Euler Theorem :

If $~\gcd(p_i,n)=1~$ then $~p^{\varphi(n)}_i \equiv 1 \pmod n$

$\bullet $ if $n$ is a prime then $p^{n-1}_i \equiv 1 \pmod n$

$\bullet $ if $n$ is a pseudoprime or composite such that $\varphi(n) \mid n-1$ then $p^{n-1}_i \equiv 1 \pmod n$

By contraposition of Euler Theorem it follows :

if $~\gcd(p_i,n) \neq 1~$ then $~p^{n-1}_i \not\equiv 1 \pmod n$

So , since $~\gcd(p_i,n) \neq 1~$ it follows $r_i \neq 1$

b) suppose $r_i=0$

According to the contraposition of Chinese Remainder Theorem :

$$\text{ iff } \begin{cases} p^{n-1}_i \not\equiv 0 \pmod {p^{a_1}_1} \\ p^{n-1}_i \not\equiv 0 \pmod {p^{a_2}_2} \\ \vdots \\ p^{n-1}_i \equiv 0 \pmod {p^{a_i}_i} \\ \vdots \\ p^{n-1}_i \not\equiv 0 \pmod {p^{a_k}_k} \end{cases} ~\text { then }~ p^{n-1}_i \not \equiv 0 \pmod {p^{a_1}_1\cdot p^{a_2}_2 \ldots p^{a_k}_k}$$

hence $~p^{n-1}_i \not \equiv 0 \pmod n ~$ and therefore $r_i \neq 0$

So , since $r_i \neq 0 \text { and } r_i \neq 1$ it follows $r_i > 1$


Question : Is my proof correct and if it is not where is a mistake ?

  • $\begingroup$ Are you saying the answers don't contain enough detail because they don't answer your actual question about whether your proof is correct? I expect nobody feels like checking your proof because there is a much shorter proof, as both Gerry Myerson and fretty have said. $\endgroup$ – Tara B Apr 13 '12 at 14:46

If $a \equiv b$ mod $n$ and $a,n$ share a common factor $m$ bigger than 1 then $m|b$.

Why is this?

Well the congruence tells you that $a = b + nk$ for some integer k, i.e. $a - nk = b$. Now $m|a$ and $m|n$ so $m|b$.

This result gives you exactly what you want.

  • $\begingroup$ right,but you didn't prove that $a \not \equiv 0 \pmod n$ $\endgroup$ – Peđa Terzić Apr 11 '12 at 13:15
  • $\begingroup$ Why does that matter? $\endgroup$ – fretty Apr 12 '12 at 22:48
  • $\begingroup$ The result is true always, I have proved it using basic divisibility. $\endgroup$ – fretty Apr 12 '12 at 22:49

If $p$ is a prime dividing $n$, and $p^a\equiv r\pmod n$, then $p$ divides $r$, so you're working too hard to show $r_i$ can't be 1.

  • $\begingroup$ OK , but is my reasoning correct ? $\endgroup$ – Peđa Terzić Apr 5 '12 at 9:59

I think that $p_i$ in the conclusion is on of the factors of n. But it is not not in the group of invertible elts mod n, and so $p_i{\phi(n)} \ne 1$. You can compute a simple example with $36 = 2^23^2, \phi(36) = 12, 2^12 \ne 1 \; mod \; 36$. Also, since $p_i$ is not invertible, it will not the case that $p_1 \times m = 1 $ for any m.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.