# Let $P$ be a prime. Show that $\exists$ $x \in \mathbb{N}$ such that $f(x) = p$ then $\exists$ $y \in \mathbb{N}$ such that $g(y) = p$

## What is given?

$$\text{Let P be a prime}$$ $$\text{Let} \space f(x)= 3x+1$$ $$\text{Let} \space g(x)= 6x+1$$

Show that: If there exists $x \in \mathbb{N}$ such that $f(x) = P$ , then there exists a $y \in \mathbb{N}$ , such that $g(y) = P$

## What have I tried?

• Given the question says 'show that', that leads me to believe I need to do a proof of sorts. I'm guessing it might be a proof by either strong induction, or just induction (or maybe just a direct proof?).
• I don't even know how to set this up
• If $f(x) =$ $3x + 1 =$ prime...for any integer $x$, then there exists an integer $y$ such that $g(y) = 6y + 1 =$ prime?

Any hints or starting points would be greatly appreciated.

$$\text{Thanks in advance!}$$

Hint:

If $x$ is odd, can $f(x)$ be prime?

• Okay, so I see $f(x)$ is not prime if x is odd. I'm not sure how to take that any further. – Rubicon May 3 '16 at 11:13
• Take the contrapositive: if $f(x)$ is prime, then …. – Bernard May 3 '16 at 11:16
• Thanks for your help Bernard. I will leave the thread unanswered for the time being in case someone would like to answer the whole proof. I have +1 though :) – Rubicon May 3 '16 at 14:27