2
$\begingroup$

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$

Q.E.D.

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

  • 0
    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.2012-04-13

3 Answers 3

0

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.

2

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.

  • 0
    OK , but is my reasoning correct ?2012-04-05
2

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.

  • 0
    The result is true always, I have proved it using basic divisibility.2012-04-12