Help with Proof

How would I go about solving this? Is the contrapositive statement:

>>> for all p, p is not prime and p > sqrt(n) and p does not divide n --> n is prime?

Thanks for anyhelp

I have no idea how to prove it, but I understand what it's asking. What's N+?

His faggot professor defined the naturals to contain 0.

You prove this by using the fundamental theorem of algebra.

It looks like this:
Assume x is a positive integer. Since x is composite, it is the product of primes. Choose one of the prime factors of x called p. Since it is a factor of x, it divides x. To prove the sqrt (x) part, look at the entire factorizaton of x.

If x = p^2 then you're done. If x =/= p^2 then x = p1*p2...*pn

Since pk*pj

Should've clafiried, N+ is a natural number excluding 0. So 1 onwards.

Wow I feel stupid it's so simple, this happens to me a lot in math class

Thank you, I understand it.

I always get confused when it comes approaching the problem and I can never decide which method to use to tackle it. Do you have tips for me?

Decide what proof is best.
Direct,induction,contradiction being the most common.

This is a direct. So in this proof we assume "p" and prove "q".

Everything we need has to be properties or other known theorems about "p".

In this case, we know it is a natural > 0 and that is has two or more prime factors. That's all you have to go off of. So you know it's going to be something relating the factors of the number.

I always end up trying contrapositive but get stuck half way through the problem. Guess its just more practice.

Also, since p is fixed, induction doesn't make sense. And whether or not you try contradiction depends on if you think the statement is true or not. If you think it's not true, contradiction is the way to go.

>pk and pj are less than sqrt (x)
but, how?

or if you think you can find a counterexample easily, it might be fucking hard

In general, contrapostives are pretty ineffective.

Yeah that is bad way of saying it
just like think about 15 = 3x5, 3

As n is composite it is divisible by at least two primes (not necessarily distinct). Lets call them [math] p,q [/math] with the property that [math] p \leq q [/math].

We can observe that [math] p^2 \leq pq \leq n [/math]. This is then summarized by [math] p^2 \leq n [/math] which implies [math] p \leq \sqrt{n} [/math]. As p is a prime divisor of n we already have that it is a divisor of n.

^

Heres another Im struggling with, if anyone could help. I proved it using contradiction by just setting m = 1 but i don't think this proof is good enough.

Fuck posted the wrong one.

use induction, it's saying 11 divides 11,22,33...
ezpz bro

oh shit nvm spoke too soon but still use induction
I would put it in sigma notation then just use algebra to prove LS = RS

We're actually just learning induction now, so I don't think we are supposed to use it for this one.

look man idk how to use LaTex but believe me this is easy as fuck using induction one sec

No need to use induction.
[math]10^{2m+1} + 1 = 10^{2m} 10 + 1 = 100^m 10 + 1 = 100^m (11 - 1) + 1 = \\11 \cdot 100^m + 1 - 100^m = 11 \cdot 100^m + 1^m - 100^m = \\ 11 \cdot 100^m + (-99)n = 11 \cdot 100^m - 11(99n) = 11(100^m - 99n)
[/math]

Where n is just the whole other bunch of stuff that appears from the difference of powers formula. That said, induction is also possible. But the most straightforward way would be to use congruences.

I understand this until 11*100^m + 1^m - 100^3,
Not sure how you got the m on the 1.

1 is equal to 1 raised to any power. I just did that to apply the difference of powers formula.

yeah nvm about the induction thing lol

because you would need strong induction for this right? Idk how to do that

No, you do not need strong induction. Simple induction is good enough, but showed that you do not even need induction. Just a little algebra.

Way easier with induction I was right, I would've got it before but I'm scatterbrained as fuck
I was confused about what N and N+ mean, I only use P for the natural numbers
Also i didn't study congruences (yet)

This is really trivial sorry

>Since pk*pj pk and pj are less than sqrt (x)
Wouldn't it be easier if you had:
x = p1*p2*....pn
Take the smallest of those pi, that is, pi

>pi2

Yea, works fine that way. I was just eyeballing it. Hadn't taken the time to word it best.

You don't need the fundamental theorem of algebra, only that every number has a prime divisor.
Prove that all divisor pairs of a number are under and over the square root, the divisor under the root is either prime, of has a prime divisor smaller than itself.
When doing number theory, don't use the fundamental theorem of algebra unless you have already proved it, since what you are trying to prove is most likely needed to prove the fundamental theorem of algebra.