GCD Proving Assistance - Get Help Now!

  • MHB
  • Thread starter Joe20
  • Start date
  • Tags
    Gcd
In summary: The base case could be $(a,b)=1$, and the inductive step could be proving that $(a,b^n) = 1 for every positive integer $n$.
  • #1
Joe20
53
1
I have encountered difficulties in solving this question. Your help is greatly appreciated!
 

Attachments

  • 1.jpg
    1.jpg
    6.4 KB · Views: 77
Mathematics news on Phys.org
  • #2
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?
 
  • #3
Thanks for the advise. I have no idea how to start.
 
  • #4
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?
 
  • #5
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: 81
  • #6
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$.
 
  • #7
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.
 

Related to GCD Proving Assistance - Get Help Now!

1. What is GCD Proving Assistance?

GCD Proving Assistance is a program designed to help individuals prove their greatest common divisor (GCD) calculations. It is specifically tailored for those who are struggling with understanding or proving their GCD calculations, providing step-by-step assistance and guidance.

2. How does GCD Proving Assistance work?

GCD Proving Assistance uses a combination of algorithms and mathematical principles to analyze and verify GCD calculations. Users can input their steps and the program will check for any errors or provide suggestions for improvement. It also offers explanations and tips to help users understand the process better.

3. Is GCD Proving Assistance free to use?

Yes, GCD Proving Assistance is completely free to use. It was created with the intention of helping individuals improve their understanding of GCD calculations, so there is no cost associated with using the program.

4. Can GCD Proving Assistance be used for all types of GCD calculations?

Yes, GCD Proving Assistance can be used for all types of GCD calculations, including simple and complex ones. It is designed to be flexible and adaptable, so it can handle a wide range of GCD problems.

5. Will GCD Proving Assistance solve the calculation for me?

No, GCD Proving Assistance is not a calculator or a solving tool. It is meant to assist and guide users in understanding and proving their own GCD calculations. Users still need to input their own steps and the program will only provide feedback and suggestions.

Similar threads

  • Linear and Abstract Algebra
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
13
Views
817
Replies
2
Views
2K
Replies
4
Views
3K
Replies
2
Views
2K
  • General Math
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Programming and Computer Science
Replies
2
Views
975
  • Linear and Abstract Algebra
Replies
3
Views
2K
  • General Math
Replies
3
Views
1K
Back
Top