Proofs in Discrete Math. forall n in N+, n composite rightarrow exists p in N+, p is prime and p <= sqrtn and p|n.

Graham Beasley 2022-07-16 Answered
Proofs in Discrete Math
n N +, n composite p N +, p is prime and p n and p|n.
Am I supposed to prove that p n and p|n when n is composite and p is prime? Could someone fix my translation if I'm wrong?
You can still ask an expert for help

Want to know more about Discrete math?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

Makenna Lin
Answered 2022-07-17 Author has 16 answers
Step 1
Our argument is based on the number of primes m that divide n. Thus if m = 1, then n is of the form n = p k wheareas p is a prime, and k 2 (for n to be composite).
Step 2
Thus n p 2 and p n . if m 2, then we can write n as n = b p r q s whereas p,q are distinct primes, and b , r , s 1 and are natural numbers. WLOG, assume p q. So: p 2 p q p r p s b p r q s = n, and p 2 n or p n . In both cases, p∣n.
Not exactly what you’re looking for?
Ask My Question

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2021-08-18
Discrete Mathematics Basics
1) Determine whether the relation R on the set of all Web pages is reflexive, symmetric, antisymmetric, and/or transitive, where (a,b)R if and only if
I) everyone who has visited Web page a has also visited Web page b.
II) there are no common links found on both Web page a and Web page b.
III) there is at least one common link on Web page a and Web page b.
asked 2021-08-02
Suppose that A is the set of sophomores at your school and B is the set of students in discrete mathematics at your school. Express each of these sets in terms of A and B.
a) the set of sophomores taking discrete mathematics in your school
b) the set of sophomores at your school who are not taking discrete mathematics
c) the set of students at your school who either are sophomores or are taking discrete mathematics
Use these symbols:
asked 2021-08-15
How many elements are in the set { 0, { { 0 } }?
asked 2021-07-28

Let A, B, and C be sets. Show that (AB)C=(AC)(BC)
image

asked 2022-07-04
What would the negation of these two statements be?
I need to negate these two statements and I believe that I have the quantifiers correct, but I'm not completely sure how to negate the math statements. I think I would keep the equations before the equal signs the same but I'm still unsure how to negate the last parts.
Here are the statements I want to negate:
Statement 1:
x , y R 0 , 9 x 2 + y 2 3 x + y .
Statement 2:
x R 0 , 25 x 2 + 9 = 5 x + 3.
asked 2021-08-09
Let consider the following algorithm: Polynomial evaluation
This algorithm evaluates the polynomial
P(x)=k=0nckxnk At the point t.
Input: The sequence of coefficients C0,C1,,Cn, the value tandn
Output: p(t)
Procedure poly(c, n, t)
If n=0 then
Return (c0)
Return (t:poly(c,n1,t)+cn)
End poly
Let bn, be the number of multiplications required to compute p(t).
a) Find the recurrence relation and initial condition for the sequence {bn}
b) Compute b1,b2andb3.
c) Solve the recurrence relation.
asked 2022-07-16
"Prove the following used the method of contradiction: The sum of two consecutive integers is always odd."
I thought this proof would be a straightforward direct proof. So, the contradiction would be "The sum of two integers is always even." Sparing the rigorous details: an integer n added to another integer ( n + 1 ) leads to ( 2 n + 1 ), which contradicts the statement, since 2 n + 1 is the representation of an odd number.
My teacher, however, proved this with two cases. The first case: a direct proof, using my strategy above, for n + ( n + 1 ). The second case, basically a similar proof to the one in the first case but now using ( n 1 ) + n. This second case is what has confused me. Isn't this step a bit redundant? Is it necessary? Does it enhance the proof, or just add superfluous information to it?

New questions

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question