Chapter 10: Problem 56

Prove that if \(m\) is odd and \(n\) is even, then gcd \((m,\)\\[n)=\operatorname{gcd}(m, n / 2)\\]

Short Answer

Expert verified

Using the properties of the gcd and odd-even numbers, it can be proved that if \(m\) is odd and \(n\) is even, then gcd(\(m,n\)) equals gcd(\(m, \frac{n}{2}\)).

Step by step solution

Understand the properties of odd, even numbers and gcd

An odd number is one which is not divisible by 2, while an even number is divisible by 2. Greatest Common Divisor (gcd) of two integers \(m\) and \(n\), not both equal to zero, is the largest positive integer that divides both \(m\) and \(n\) without a remainder.

Assume \(m\) and \(n\) are both not zero

Since gcd is defined for two integers not both equal to zero, let’s assume \(m\) and \(n\) are both not zero. Also, \(m\) is odd and \(n\) is even as given in the problem statement.

Define gcd and equality

If \(d\) is gcd(\(m, n\)), then \(d\) divides \(m\) and \(d\) also divides \(n\). Hence, it must divide \(\frac{n}{2}\) as well because \(n\) is even. Also, if \(d'\) is a divisor of both \(m\) and \(\frac{n}{2}\), given that \(m\) is odd and \(\frac{n}{2}\) is half of an even integer, \(2d'\) would also be a divisor of \(n\). Hence, \(d'\) is a divisor of both \(m\) and \(n\). This means \(d = d'\) and hence gcd(\(m, n\)) = gcd(\(m, \frac{n}{2}\)).

Conclusion

From the above steps, we can conclude that if \(m\) is odd and \(n\) is even, then gcd(\(m,n\))=gcd(\(m, \frac{n}{2}\)).

Unlock Step-by-Step Solutions & Ace Your Exams!

Full Textbook Solutions
Get detailed explanations and key concepts
Unlimited Al creation
Al flashcards, explanations, exams and more...
Ads-free access
To over 500 millions flashcards
Money-back guarantee
We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

Recommended explanations on Computer Science Textbooks

View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Prove that if \(m\) is odd and \(n\) is even, then gcd \((m,\)\\[n)=\operatorname{gcd}(m, n / 2)\\]

Short Answer

Step by step solution

Understand the properties of odd, even numbers and gcd

Assume \(m\) and \(n\) are both not zero

Define gcd and equality

Conclusion

One App. One Place for Learning.

Most popular questions from this chapter

Recommended explanations on Computer Science Textbooks

Issues in Computer Science

Game Design in Computer Science

Data Structures

Data Representation in Computer Science

Functional Programming

Databases

Study anywhere. Anytime. Across all devices.