g.c.d.(r,s)

Results 1 to 8 of 8

- Jan 5th 2009, 11:32 PM #1

- Jan 6th 2009, 04:25 AM #2

- Jan 6th 2009, 06:46 AM #3

- Jan 6th 2009, 07:11 AM #4

- Jan 6th 2009, 07:25 AM #5

- Jan 6th 2009, 01:55 PM #6

- Joined
- Nov 2005
- From
- New York City
- Posts
- 10,616
- Thanks
- 10

The original poster asked to prove $\displaystyle \gcd( r,s ) = 1$ as

**integers**not as polynomials.

If it was polynomials then the result works since $\displaystyle x^4+x^3+x^2+x+1$.

Consider $\displaystyle f=x+1$ and $\displaystyle g=(x+3)^2$ then $\displaystyle \gcd (f(x),g(x))=1$.

However if $\displaystyle x=1$ then $\displaystyle f(1) = 2$ and $\displaystyle g(1) = 16$ but $\displaystyle \gcd( f(1), g(1)) \not = 1$.

----

To solve this problem we need to know a theorem:

Let $\displaystyle a,n,m>0$ then $\displaystyle \gcd( a^n -1, a^m - 1) = a^d - 1$ where $\displaystyle d=\gcd(n,m)$.

This means, $\displaystyle \gcd( m^5 - 1, m^{16} - 1) = m - 1$ since $\displaystyle \gcd(5,16)=1$.

But then, $\displaystyle \gcd( \tfrac{m^5 - 1}{m-1} , \tfrac{m^{16} - 1}{m-1} ) = 1$.

This completes the proof since $\displaystyle \tfrac{m^5 - 1}{m-1} = 1 + m + ... + m^4$ and $\displaystyle \tfrac{m^{16}-1}{m-1} = 1 + m + ... + m^{15}$.

- Jan 7th 2009, 03:30 AM #7

- Jan 7th 2009, 07:37 AM #8

- Joined
- Nov 2005
- From
- New York City
- Posts
- 10,616
- Thanks
- 10