Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
    
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. –  Tara B Apr 13 '12 at 14:46

3 Answers 3

up vote 2 down vote accepted
+25

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.

share|improve this answer
    
right,but you didn't prove that $a \not \equiv 0 \pmod n$ –  pedja Apr 11 '12 at 13:15
    
Why does that matter? –  fretty Apr 12 '12 at 22:48
    
The result is true always, I have proved it using basic divisibility. –  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.

share|improve this answer
    
OK , but is my reasoning correct ? –  pedja 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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