User Name Remember Me? Password

 Abstract Algebra Abstract Algebra Math Forum

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!
Attached Images 1.jpg (14.8 KB, 22 views) 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

Quote:
 Originally Posted by Alexis87 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?
Because I'm suggesting you to do a proof by contradiction/contrapositive. 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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post erblina zeqiri Algebra 1 January 5th, 2015 04:15 PM spuncerj Pre-Calculus 1 November 28th, 2014 04:43 PM medos Algebra 5 October 31st, 2012 03:54 PM MathematicallyObtuse Algebra 2 February 5th, 2011 03:59 PM firstsin Abstract Algebra 0 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top      