GCD Proving Assistance - Get Help Now!

  • Context: MHB 
  • Thread starter Thread starter Joe20
  • Start date Start date
  • Tags Tags
    Gcd
Click For Summary

Discussion Overview

The discussion revolves around proving properties related to the greatest common divisor (GCD) using mathematical induction. Participants are seeking assistance with the initial steps of the proof and exploring different approaches to establish the relationship between GCDs of integers and their powers.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant expresses difficulty in starting the proof and requests help.
  • Another participant emphasizes the importance of showing progress in problem-solving to facilitate better assistance.
  • A suggestion is made that the proof involves a base case and an induction hypothesis, prompting a question about what the base case could be.
  • A hint is provided regarding the use of the condition for $(a,b) = 1$ and its implications for proving $(a,b^n) = 1$ for all positive integers $n$.
  • There is a contention regarding the base case for the induction proof, with one participant asserting that it should be $(a,b) = 1$ rather than $(a,b^2) = 1$.
  • Another participant clarifies that their suggestion regarding $(a,b^2) = 1$ was intended as a technique for the inductive step, not as the base case.

Areas of Agreement / Disagreement

Participants do not appear to reach a consensus on the appropriate base case for the induction proof, with competing views on whether it should be $(a,b) = 1$ or $(a,b^2) = 1$. The discussion remains unresolved regarding the best approach to take.

Contextual Notes

There are unresolved assumptions about the definitions and properties of GCDs that may affect the proof's structure. The discussion also reflects varying interpretations of the inductive proof process.

Joe20
Messages
53
Reaction score
1
I have encountered difficulties in solving this question. Your help is greatly appreciated!
 

Attachments

  • 1.jpg
    1.jpg
    6.4 KB · Views: 128
Mathematics news on Phys.org
Hello Alexis87 and welcome to MHB! :D

We ask that our users show their progress (work thus far or thoughts on how to begin) when posting questions. This way our helpers can see where you are stuck or may be going astray and will be able to post the best help possible without potentially making a suggestion which you have already tried, which would waste your time and that of the helper.

Can you post what you have done so far?
 
Thanks for the advise. I have no idea how to start.
 
We're talking about a proof by induction.
That means that the proof starts with a base case, which is followed by an induction hypothesis.
What could the base case be?
 
Alexis87 said:
I have encountered difficulties in solving this question. Your help is greatly appreciated!
A few hints to get you started:

The neatest way to work with GCDs is to use the fact that the condition for $(a,b) = 1$ is that there exist integers $x,y$ such that $ax+by=1$.

Suppose that condition holds. Then (multiplying through by $by$) it follows that $axby + b^2y^2 = by = 1-ax.$ Therefore $$a(xby + x) + b^2y^2 = 1.$$ That equation is of the form $aX + b^2Y = 1$, which shows that $(a,b^2) = 1.$

Can you use that as the basis for an inductive proof that $(a,b^n) = 1$ for all $n$?
 

Attachments

  • 1.jpg
    1.jpg
    6.4 KB · Views: 135
Opalg said:
That equation is of the form $aX + b^2Y = 1$, which shows that $(a,b^2) = 1.$

Can you use that as the basis for an inductive proof that $(a,b^n) = 1$ for all $n$?
I think the basis for an induction proof that $(a,b^n)=1$ for every positive integer $n$ is $(a,b)=1$ and not $(a,b^2)=1$.
 
Evgeny.Makarov said:
I think the basis for an induction proof that $(a,b^n)=1$ for every positive integer $n$ is $(a,b)=1$ and not $(a,b^2)=1$.
Yes, of course. But I was not implying that the base case should be $(a,b^2)=1$. What I was suggesting was a technique that might be used for proving the inductive step.
 

Similar threads

MHB How can I prove that gcd(a,b) is an integer and gcd(a/b, b/h) = 1?
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Questions regarding Kurepa's Conjecture
  • · Replies 1 ·
Replies
1
Views
2K
MHB Finding the Greatest EVEN Factor of X: Solving the GCD of m,n=2
  • · Replies 19 ·
Replies
19
Views
5K
Undergrad Understanding the Results of gcd(x,n)
  • · Replies 8 ·
Replies
8
Views
2K
Proving an integer is composite
  • · Replies 13 ·
Replies
13
Views
1K
MHB Prove the minimum is greater than or equal to 8
  • · Replies 2 ·
Replies
2
Views
2K
MHB How do I solve this Diophantine equation using modulo?
  • · Replies 6 ·
Replies
6
Views
3K
MHB Eulers phi function, orders, gcd
  • · Replies 2 ·
Replies
2
Views
2K
MHB GCD: Fastest Method to Simplify Fractions
  • · Replies 4 ·
Replies
4
Views
2K
MHB Can GCD of m and n be forced to equal 1 for given equations and conditions?
  • · Replies 3 ·
Replies
3
Views
4K