Uhh help with this proof then x is prime .

[charmedbeauty]

uhh! help with this proof """" then x is prime""".

Homework Statement

For a positive integer x≥2.

"if x is not divisible by any positive integer n satisfying 2≤n≤√x then x is a prime number"

a) show that the above statement is true .

b) Is the statement still true if the condition on n is replaced by 2≤n<√x ??

Homework Equations

The Attempt at a Solution

Well firstly I really have problems with proofs in general, but

x≥4

so x can be [4,5,6,7,...∞)

so by definition of prime number x--> x/x and x/1

but I really don't know how to approach this
I know its true because n= [2,3,4,5...∞)
and so the only numbers not possibly divisible by n are primes, Since n can be any positive integer ≥2, and Since x≠1.

But how do I put it in mathematical terms??
HELP!

 

[Dick]

Try and prove the contrapositive. If x is NOT prime then there IS a positive integer satisfying 2≤n≤√x that divides x.

 

[D H]

An integer x>1 is composite if there exists some number 1<n<x that divides n. The integer x is prime if not such number n exists. What this is this theorem is telling you is that you don't have to look at all integers between 2 and x-1 (inclusive). You only need to look at those between 2 and √x (inclusive).

Hint: Suppose n is an integer that divides x. In other words, m=x/n is an integer. What can you say about m if √x≤n<x?

 

[charmedbeauty]

An integer x>1 is composite if there exists some number 1<n<x that divides n. The integer x is prime if not such number n exists. What this is this theorem is telling you is that you don't have to look at all integers between 2 and x-1 (inclusive). You only need to look at those between 2 and √x (inclusive).

Hint: Suppose n is an integer that divides x. In other words, m=x/n is an integer. What can you say about m if √x≤n<x?

Well mn=x so x is not a prime if this condition is satisfied.

and m can be any positive integer >1 since m=x/n which is greater than 1 since n<x, and n,x are positive integers.

But I don't really understand when exactly this condition satisfies, namely, mn=x, Since to me mn could be less than, equal, or greater than x.

Since m>1 and n<x. There are values of x,m,n that satisfy all three conditions ie, <,=,>.

 

[charmedbeauty]

Well mn=x so x is not a prime if this condition is satisfied.

and m can be any positive integer >1 since m=x/n which is greater than 1 since n<x, and n,x are positive integers.

But I don't really understand when exactly this condition satisfies, namely, mn=x, Since to me mn could be less than, equal, or greater than x.

Since m>1 and n<x. There are values of x,m,n that satisfy all three conditions ie, <,=,>.

On second thoughts m>x so since n≥2 then mn>x.

So I think this tells me that if x does not divide some n≥2 then x is not prime?? Although I think for this to be true I need the eqn to be mn=x? I am confused.

 

[HallsofIvy]

On second thoughts m>x so since n≥2 then mn>x.

So I think this tells me that if x does not divide some n≥2 then x is not prime??

Surely this is not what you meant to say? Any x, prime or not, divides 2x, for example.

It is true that if x is not divisible by some [itex]n\ge 2[/itex] (except x itself) then x is prime.

Although I think for this to be true I need the eqn to be mn=x? I am confused.

If x= mn and [itex]m>\sqrt{x}[/itex], what can you say about n?

As for "b) Is the statement still true if the condition on n is replaced by 2≤n<√x ??",
consider x= 9.

 

[charmedbeauty]

If x= mn and [itex]m>\sqrt{x}[/itex], what can you say about n?

As for "b) Is the statement still true if the condition on n is replaced by 2≤n<√x ??",
consider x= 9.

if x=mn and m>√x

then all I can say from this statement is that mn is > √x. And that n is <√x, Since mn=x. I'm still really lost?

 

[Office_Shredder]

And that n is <√x, Since mn=x.

If x is composite, we can factor it as x=mn we have two possibilities
1) m< √x
2) n< √x

In both cases, we see that if x is composite, it is divisible by a number which is no larger than √x, which is exactly what you wanted to prove (after you change some strict inequalities to weak inequalities)

 

[charmedbeauty]

If x is composite, we can factor it as x=mn we have two possibilities
1) m< √x
2) n< √x

In both cases, we see that if x is composite, it is divisible by a number which is no larger than √x, which is exactly what you wanted to prove (after you change some strict inequalities to weak inequalities)

Ok thanks Office Shredder and others that helped...

so does this proof look correct now.

given ---> 2≤n≤√x and x≥2

So n≥2 from above inequality.

Suppose x is not prime, then, by definition of a prime

m = x/n for some integers m and x,n both≥2

hence, x=mn

Now either n< √x or m<√x or m=√x iff n=√x

In either case x/m or x/n

But if x is prime, by definition, x cannot divide m or n where m,n≥2

Hence m is prime iff x does not divide n where 2≤n≤√x

proof finished.

and for part b)

let x=9

therefore, 2≤n<3

Now x is prime iff x does not divide n for some integer n satisfying above inequality.

but 9 does not divide 2 and when x =9, n must =2 (satisfying the above inequality).

Hence x is prime. Contradiction. 9 is not prime. Therefore above inequality does not hold.

 

[HallsofIvy]

and for part b)

let x=9

therefore, 2≤n<3

Now x is prime iff x does not divide n for some integer n satisfying above inequality.

but 9 does not divide 2 and when x =9, n must =2 (satisfying the above inequality).

Hence x is prime. Contradiction. 9 is not prime. Therefore above inequality does not hold.

I have no idea what you are trying to do. All you need to note is that 9 is not prime and [itex]\sqrt{9}=3[/itex]. "[itex]2\le x< \sqrt{9}= 3[/itex]" is true only for x= 2 and 2 does not divide 9. End of counter example.

 

[charmedbeauty]

I have no idea what you are trying to do. All you need to note is that 9 is not prime and [itex]\sqrt{9}=3[/itex]. "[itex]2\le x< \sqrt{9}= 3[/itex]" is true only for x= 2 and 2 does not divide 9. End of counter example.

Ok thanks, undestood!