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>1.


Question and Answers Forum

All Questions Topic List
Number Theory Questions
Previous in All Question Next in All Question
Previous in Number Theory Next in Number Theory
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 .$
Terms of Service
Privacy Policy
Contact: info@tinkutara.com

Question and Answers Forum