
Abstract Algebra Abstract Algebra Math Forum 
 LinkBack  Thread Tools  Display Modes 
January 20th, 2018, 06:20 AM  #1 
Senior Member Joined: Sep 2011 Posts: 105 Thanks: 1  Mathematical induction in Number Theory
I have encountered difficulties in solving this question. Your help is greatly appreciated!

January 20th, 2018, 06:23 AM  #2 
Senior Member Joined: Oct 2009 Posts: 884 Thanks: 340 
Let's take $n=2$ for the moment. Assume $(a,b^2) = d \neq 1$. What do you know then by definition of the gcd?

January 20th, 2018, 06:47 AM  #3 
Senior Member Joined: Sep 2011 Posts: 105 Thanks: 1 
GCD is the greatest common divisor, d of both a and b where a/d and b/d. May I ask why use that assumption of not equal to 1? How would you continue from there? 
January 20th, 2018, 08:33 AM  #4 
Senior Member Joined: Oct 2009 Posts: 884 Thanks: 340  
January 20th, 2018, 02:41 PM  #5 
Senior Member Joined: Sep 2016 From: USA Posts: 670 Thanks: 440 Math Focus: Dynamical systems, analytic function theory, numerics 
Induction does not seem (to me) to be a very natural way to approach this proof. That isn't to say that it can't be done via induction. Here is a sketch. (1) First prove the following claim: Suppose $(a,b) = 1$ and $(a,c) = 1$, then $(a,bc) = 1$. (2) Now, fix $a,b$ and assume $(a,b) = 1$. Take $n=1$ for the base case which is complete by assumption. (3) Assume inductively that $(a,b^n) = 1 $ holds for some $n \in \mathbb{N}$. Now, set $c = b^n$ so that $(a,b) = (a,c) = 1$ holds and apply the claim from (1). This proves by induction that $(a,b^{n+1}) = 1$ for every $n \in \mathbb{N}$. (4) Apply a similar argument as in (3) to prove that for $n\in \mathbb{N}$ fixed, $(a^m,b^n) = 1$ for every $m \in \mathbb{N}$ which concludes the proof. 
January 27th, 2018, 07:13 AM  #6 
Senior Member Joined: Sep 2011 Posts: 105 Thanks: 1 
Hi SDK, for step 4 do I write like the following? : suppose (a,c)=1 and (p,c) =1 then (ap, c) =1 since (a , b^n) = 1 as proven earlier, assume that (a^m, b^n) = 1 holds. Let p = a^m so that (a,c) = (ap, c) = 1 where c = b^n. Therefore, (a^m, b^n) = 1 fpr every m, n is an element of natural numbers. 
January 27th, 2018, 07:14 AM  #7 
Senior Member Joined: Sep 2011 Posts: 105 Thanks: 1 
Hi SDK, for step 4 do I write like the following? : suppose (a,c)=1 and (p,c) =1 then (ap, c) =1 since (a , b^n) = 1 as proven earlier, assume that (a^m, b^n) = 1 holds. Let p = a^m so that (a,c) = (ap, c) = 1 where c = b^n. Therefore, (a^m, b^n) = 1 fpr every m, n is an element of natural numbers. 

Tags 
induction, mathematical, number, theory 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
mathematical induction  erblina zeqiri  Algebra  1  January 5th, 2015 04:15 PM 
Mathematical Induction.  spuncerj  PreCalculus  1  November 28th, 2014 04:43 PM 
mathematical induction  medos  Algebra  5  October 31st, 2012 03:54 PM 
Mathematical Induction  MathematicallyObtuse  Algebra  2  February 5th, 2011 03:59 PM 
Mathematical Induction help please.  firstsin  Abstract Algebra  0  December 31st, 1969 04:00 PM 