# Counter definition of prime number?

• (2 Pages)
• 1
• 2

## 22 Replies - 2144 Views - Last Post: 24 June 2013 - 01:12 PM

### #1 deprosun

• D.I.C Regular

Reputation: 0
• Posts: 307
• Joined: 16-November 10

# Counter definition of prime number?

Posted 24 June 2013 - 09:49 AM

This is actual definition of Prime number according to my book:
P(x) ↔ ((x>1) Λ (∀y: D(y,x) → (y=1 ∨ y=x)))

This is my interpretation, is it correct?
P(x) ↔ ((x>1) Λ (¬∃y: D(y,x) → (¬(y=1) ∧ ¬(y=x))))
Is This A Good Question/Topic? 0

## Replies To: Counter definition of prime number?

### #2 jon.kiparsky

• Pancakes!

Reputation: 9526
• Posts: 16,476
• Joined: 19-March 11

## Re: Counter definition of prime number?

Posted 24 June 2013 - 09:53 AM

This looks like a correct application of de Morgan's law. However, I think there may be a flaw in the implication side.

Let me put it in English and you can see what you think:

X is prime iff x is positive and (if there exists no y which divides x evenly then y is not 1 and y is not x)

This post has been edited by jon.kiparsky: 24 June 2013 - 09:57 AM

### #3 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11789
• Posts: 44,301
• Joined: 27-December 08

## Re: Counter definition of prime number?

Posted 24 June 2013 - 09:54 AM

No. The contrapositive would be valid. So if y != 1 and y != x, then y does not divide x.

You are only inverting the necessary condition, not the sufficient condition, which is only half of the inverse and still incorrect.

Edit- Can you write out your definition in plain English? The mathematical representation of your definition is bulky and hard to work with. I'd be interested in hearing your thoughts more plainly.

Quote

This is my interpretation, is it correct?
P(x) ↔ ((x>1) Λ (¬∃y: D(y,x) → (¬(y=1) ∧ ¬(y=x))))

Edit again- I would agree with how Jon read this. I'm just not a fan of it because you're mixing up the necessary and sufficient conditions.

Quote

X is prime iff x is positive and (if there exists no y which divides x evenly then y is not 1 and y is not x)

### #4 deprosun

• D.I.C Regular

Reputation: 0
• Posts: 307
• Joined: 16-November 10

## Re: Counter definition of prime number?

Posted 24 June 2013 - 10:21 AM

So..
P(x) ↔ ((x>1) Λ (¬∃y: D(y,x) → (¬(y=1) ∧ ¬(y=x))))

According to me it says, x is a prime number iff x is greater than 1 and there does NOT exists a number such that if it divides x then the number does not equal x and 1.

This post has been edited by deprosun: 24 June 2013 - 10:26 AM

### #5 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11789
• Posts: 44,301
• Joined: 27-December 08

## Re: Counter definition of prime number?

Posted 24 June 2013 - 10:51 AM

Your sufficient condition will never be true though.

Quote

If there does not exist a y that divides x

Clearly, let y = 1 or y = x. Thus, your implication does not hold.

Again, order of implication matters. If p -> q is a valid implication, then ~q -> ~p is a valid implication as well.

When negating a logical statement, if you have a universal quantifier "for all x, p(x)", the negation is "there exists an x such that ~p(x)." Similarly, an existential quantifier is negated by a universal quantifier. So "if there exists an x such that p(x)," the negation is "for all x, ~p(x)."

### #6 deprosun

• D.I.C Regular

Reputation: 0
• Posts: 307
• Joined: 16-November 10

## Re: Counter definition of prime number?

Posted 24 June 2013 - 11:34 AM

I think i am thinking too much

### #7 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11789
• Posts: 44,301
• Joined: 27-December 08

## Re: Counter definition of prime number?

Posted 24 June 2013 - 11:38 AM

Just another note as well. Make sure you specify your domain of discourse in your definitions. I'm assuming you're talking about the integers. You get some interesting results when you look at complex numbers and primality. In fact, analytic number theory is a pretty well-defined field.

### #8 deprosun

• D.I.C Regular

Reputation: 0
• Posts: 307
• Joined: 16-November 10

## Re: Counter definition of prime number?

Posted 24 June 2013 - 11:39 AM

I am working with naturals here as of now

### #9 deprosun

• D.I.C Regular

Reputation: 0
• Posts: 307
• Joined: 16-November 10

## Re: Counter definition of prime number?

Posted 24 June 2013 - 12:35 PM

I have one more,
The statement says: A prime number like 7 is relatively prime to any natural number except one of its own multiple.
On a side note: Relatively Prime is when GCD(x,y)=1.

I wanted to translate the bolded statement into predicates as following:
P(x) defines that x is prime
GCD(P(x),y) == 1 → (∀y: ¬D(x,y))

Correct?

### #10 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11789
• Posts: 44,301
• Joined: 27-December 08

## Re: Counter definition of prime number?

Posted 24 June 2013 - 12:41 PM

It's not a universal statement though. And the quantifier should be on the sufficient condition, not the necessary condition. When talking about coprimality, you are talking about two distinct integers (both existential). The only number that is relatively prime to all the naturals is 1.

### #11 deprosun

• D.I.C Regular

Reputation: 0
• Posts: 307
• Joined: 16-November 10

## Re: Counter definition of prime number?

Posted 24 June 2013 - 12:43 PM

oohh!! umm getting there..
So you're saying my statement is incorrect? How many points will i get out of 10? />

### #12 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11789
• Posts: 44,301
• Joined: 27-December 08

## Re: Counter definition of prime number?

Posted 24 June 2013 - 12:47 PM

Probably not a lot. You seem to be able to articulate the definitions, but you need work on the flow of logic, as well as necessary vs. sufficient conditions.

### #13 deprosun

• D.I.C Regular

Reputation: 0
• Posts: 307
• Joined: 16-November 10

## Re: Counter definition of prime number?

Posted 24 June 2013 - 12:48 PM

I think that what I need to learn here then before i go further. Any online documents you suggest?

### #14 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11789
• Posts: 44,301
• Joined: 27-December 08

## Re: Counter definition of prime number?

Posted 24 June 2013 - 12:50 PM

What class are you in? What textbooks are you using? Those can be good resources sometimes.

Jimmy Arnold's book is used for the proofs class at my school. Martin Day has a textbook as well, though I prefer Arnold's. Both are free.

http://www.math.vt.e...k/3034Chap1.pdf

### #15 deprosun

• D.I.C Regular

Reputation: 0
• Posts: 307
• Joined: 16-November 10

## Re: Counter definition of prime number?

Posted 24 June 2013 - 12:54 PM

That look clean! I had Kenneth H. Rosen last semester. Now I am using my current professor's own published book