If b | a(n-a) can one say b | n

  • Thread starter icantadd
  • Start date
In summary, we can prove that b divides n! based on the given condition b | a!(n-a)! by showing that a!b! divides (a+b)!, where b is a divisor of n! and a is a positive integer. This can be shown using induction and the property that m | n <=> n = am.
  • #1
icantadd
114
0

Homework Statement



Suppose b | a!(n-a)! and prove that b | n!

Homework Equations



m | n <=> n = am

The Attempt at a Solution



b | a!(n-a)! ,so that
a!(n-a)! = bs, so that
a!(n-a)!(nCa) = bs(nCa) (nCa is a combinations of n items)
n! = bs(nCa)
And so b is obviously a divisor of n!
 
Physics news on Phys.org
  • #2
We can show a!b! divides (a+b)!

WLOG assume a > b,

First, make the following observation,

[tex] \frac{(a+b)!}{a!b!} = \frac{(a+b)(a+b-1) \ldots (b+1) b!}{a!b!} = \frac{(a+b)(a+b-1) \ldots (b+1)}{a!}[/tex]

Now, by induction on b, if b=1,
[tex] (a+b)! = (a+1)! = (a+1)a! = (a+1)a!b![/tex]
So by definition we have that a!b! divides (a+b)!

So assume the result holds for b, and we will show the result holds for b+1. Now, consider,

[tex] \frac{(a+b+1)!}{a!(b+1)!} = \frac{(a+b+1)(a+b)(a+b-1) \ldots (b+1)!}{a!(b+1)!}
[/tex]


Next, we will be a bit tricky by bracketing things off right.


[tex] \frac{(a+b+1)(a+b)(a+b-1) \ldots (b+1)b!}{(b+1)!a!} = \frac{(a+b+1)b!(a+b)(a+b-1) \ldots (b+1)}{(b+1)!a!} [/tex]

Now, it suffices to show the above is an integer. First let's consider what our inductive hypothesis tells us. It says that a! divides (a+b)(a+b-1) ... (b+1). So there is some integer d such that,

[tex] \frac{(a+b)(a+b-1) \ldots (b+1)}{a!} = d [/tex]

Now we have to show the following is an integer,but

[tex] \frac{(a+b+1)b!}{(b+1)!} = \frac{(a + (b+1))b!}{(b+1)!} = \frac{ab! + (b+1)!}{(b+1)!}[/tex]

Err, ?
 

Related to If b | a(n-a) can one say b | n

1. Can b divide n if b divides a(n-a)?

Yes, if b divides both a and (n-a), then it also divides their sum (a + (n-a) = n). Therefore, b can divide n.

2. What is the relationship between b dividing a and b dividing n?

If b divides a, then a is a multiple of b. This means that a can be expressed as b times some integer. Similarly, if b divides n, then n is a multiple of b and can be expressed as b times some integer. Therefore, b divides both a and n, and their product (a(n-a)) since it is the product of two multiples of b.

3. Is (n-a) always divisible by b if b divides a and b divides n?

Yes, if b divides both a and n, then (n-a) is also a multiple of b. This is because (n-a) = n - a, and we know that b divides both n and a. Therefore, b can divide the difference between them, which is (n-a).

4. What is the significance of b dividing a(n-a)?

The fact that b divides a(n-a) is an indication that b is a common factor of both a and (n-a). This can be useful in simplifying mathematical expressions and solving equations involving b, a, and n.

5. Can b divide n if b does not divide a and b does not divide (n-a)?

No, if b does not divide both a and (n-a), then it cannot divide their product (a(n-a)). Therefore, b cannot divide n in this scenario.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
696
  • Calculus and Beyond Homework Help
Replies
1
Views
673
  • Calculus and Beyond Homework Help
Replies
3
Views
910
  • Calculus and Beyond Homework Help
Replies
3
Views
671
  • Calculus and Beyond Homework Help
Replies
3
Views
846
  • Calculus and Beyond Homework Help
Replies
2
Views
485
  • Calculus and Beyond Homework Help
Replies
4
Views
617
  • Calculus and Beyond Homework Help
Replies
1
Views
668
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
561
Back
Top