Chapter 10: Problem 40

Show that if \(q\) is a factor of \(n\) and \(k\) is the order of \(q\) in \(n,\) then \(q^{k} | B(n, q),\) where \(B(n, q)\) denotes the binomial coefficient.

Short Answer

Expert verified

The statement is true; if \(q\) is a factor of \(n\) and \(k\) is the order of \(q\) in \(n,\) then \(q^{k}\) does indeed divide \(B(n, q)\). This has been proven by showing that both \(n!\) and \(q!\) are divisible by \(q^k\), and by then using the definition of the binomial coefficient.

Step by step solution

Understanding notation and terms

First, let's clarify the terms: \n - A factor of a number is a number that divides the original number without leaving a remainder. In this case, \(q\) is a factor of \(n\).\n - The order of a number (in this case, \(q\) in relation to \(n\)) refers to the highest power that \(q\) can be raised to before it no longer divides \(n\).\n - The binomial coefficient \(B(n, q)\) is defined as \(n!/(q!(n-q)!)\), where the '!' denotes factorial, the product of all positive integers up to that number.

Substituting the binomial coefficient

Proofs often require substitution of equivalent terms. In this case, we substitute the binomial coefficient \(B(n, q)\) with its definition, \(n! / (q!(n-q)!)\).

Constructing the Divisibility Argument

Now we can construct our divisibility argument.\n From the definition of order, it is known that \(q^k\) divides \(n!\). Furthermore, since \(k\) is the highest power to which \(q\) can be raised and still divide \(n\), it can be inferred that \(q^k\) does not divide \((n-q)!\). Therefore, only factors of \(n!\) are divisible by \(q^k\).\n It is also worth noting that \(q^k\) divides \(q!\) since \(k\) is the order of \(q\) in \(n\).\n Hence, \(q^k\) divides the ratio of \(n!\) and \(q!(n-q)!\), proving our initial hypothesis that \(q^k | B(n, q)\).

Concluding the Proof

We have shown that \(q^k\) is a factor of the binomial coefficient \(B(n, q)\) under the given conditions, as required. This concludes the proof.

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.

Show that if \(q\) is a factor of \(n\) and \(k\) is the order of \(q\) in \(n,\) then \(q^{k} | B(n, q),\) where \(B(n, q)\) denotes the binomial coefficient.

Short Answer

Step by step solution

Understanding notation and terms

Substituting the binomial coefficient

Constructing the Divisibility Argument

Concluding the Proof

One App. One Place for Learning.

Most popular questions from this chapter

Recommended explanations on Computer Science Textbooks

Issues in Computer Science

Computer Systems

Algorithms in Computer Science

Data Structures

Game Design in Computer Science

Theory of Computation

Study anywhere. Anytime. Across all devices.