If-n-p-q-Z-and-p-and-q-are-coprimes-then-prove-that-HCF-of-n-p-1-and-n-q-1-is-n-1-Assume-n-gt-1-

Question Number 3296 by prakash jain last updated on 09/Dec/15

If n, p, q \in Z^{+} and p and q are coprimes,

then prove that HCF of (n^{p} - 1) and (n^{q} - 1) is (n - 1) .

Assume n > 1 .

Commented by Rasheed Soomro last updated on 10/Dec/15

T h i s m e a n s \frac{n^{p} - 1}{n - 1} a n d \frac{n^{q} - 1}{n - 1} a r e c o p r i m e .

I - E I f a n y d ∣ \frac{n^{p} - 1}{n - 1} t h e n d ∤ \frac{n^{q} - 1}{n - 1} d > 1

Commented by prakash jain last updated on 10/Dec/15

Yes .

Commented by Rasheed Soomro last updated on 10/Dec/15

E a s i l y c a n b e s h o w n t h a t

(n - 1) ∣ (n^{p} - 1) \land (n - 1) ∣ (n^{q} - 1)

i e n - 1 i s a c o m m o n d i v i s o r .

N o w w e h a v e t o p r o v e t h a t a n y n u m b e r g r e a t e r t h a n

n - 1 {c a n}^{'} t d i v i d e b o t h .

L e t k > 0 a n d k \in N \Rightarrow n + k - 1 > n - 1

W e h a v e t o p r o v e :

n^{p} - 1 ≇ 0 (m o d n + k - 1) \land n^{p} - 1 ≇ 0 (m o d n + k - 1)

∵ k \in N t h e r f o r e p e r h s p s m a t h e m a t i c a l i n d u c t i o n

c o u l d h e l p .

Answered by prakash jain last updated on 11/Dec/15

After removing common factor (n - 1) .

A = \underset{j = 1}{\sum^{p}} n^{j - 1}, B = \underset{j = 1}{\sum^{q}} n^{j - 1}

Let us say d > 1 is common factor in A a n d B .

clearly d ∤ n since in that \frac{A}{d} \in N will imply

\frac{1}{d} \in N .

l e t u s a s s u m e p > q .

s i n c e d divides B = \underset{j = 1}{\sum^{q}} n^{j - 1} there exists k ⩽ q

such that d divides \underset{j = 1}{\sum^{k}} n^{j - 1}, let us smallest

value of k for which d divides \underset{j = 1}{\sum^{k}} n^{j - 1} is i .

Clearly i > 1 .

i f q = m i + r, r < i

B = \underset{j = 1}{\sum^{m i + r}} n^{j - 1} = \underset{x = 0}{\sum^{m - 1}} n^{x i} [\underset{j = 1}{\sum^{i}} n^{j - 1}] + n^{m i} \underset{j = 1}{\sum^{r}} n^{j - 1}

i f d d i v i d e s B then d d i v i d e s n^{m i} \underset{j = 1}{\sum^{r}} n^{j - 1} s i n c e

d ∤ n^{m i} \Rightarrow d d i v i d e s \underset{j = 1}{\sum^{r}} n^{j - 1}

Sincd r < i, it contradicts that

i is the smallest value for k where \underset{j = 1}{\sum^{k}} n^{j - 1}

is divisible by d . So r must be equal to 0 .

\Rightarrow q = m i

s i m i l a r l y p = k i

So i > 1 is common factor between q and p .

c o n t r a d i c t s p a n d q are coprime .

hence no common factor between A and B .