My Math Forum Mathematical induction in Number Theory
 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 Display Modes Linear 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