New deterministic primality test for numbers of the form $p\cdot 2^n + 1$ Edit: Sorry, there was an error. 
Old Claim (not true because there is a counter-example):

Let $p$ be prime. Let $n \in \left\{1, 2, 3, ...\right\}$. Then $N =
p\cdot 2^n+1$ is prime, if and only if it holds the  congruence $3^{N-1} \equiv 1\ ($mod $N)$.

The right claim goes as follows

Let $p$ be prime. Let $n \in \left\{1, 2, 3, ...\right\}$. Then $N =
p\cdot 2^n+1$ is prime, if and only if it holds the  congruence $3^{(N-1)/2} \equiv \pm1\ ($mod $N)$.

If the claim is true, we would have a fast deterministic test for numbers of the form $p\cdot2^n + 1$. That means, with small $p$ and large $n$, we could generate huge prime numbers, similar to Mersenne primes or Fermat primes. 
There are a lot of questions:


*

*Is a proof possible? 

*If yes, can the expression $3^{(N-1)/2}$ faster evaluated than Mersenne test?

*Computing $3^{(N-1)/2}$: Are there faster methods than binary modular exponentiation?

 A: Counterexample : $N=356387\cdot 2^{11}+1=12289\cdot 59393\;$ while $\;3^{N-1}\equiv 1\pmod{N}$
It is interesting to observe 


*

*$\;2^{N-1}\not\equiv 1\pmod{N}\;$ 

*$\;12289=3\cdot 2^{12}+1\;$ while $\;59393=29\cdot 2^{11}+1\;$ so that both prime factors are (minimal)
$2^n$ safe-primes : OEIS A051900.

A:  Modified claim (Euler pseudoprime to base $3$)
Consider $\,N =p\cdot 2^n+1\,$ with $p$ an odd prime and $n$ a positive integer then according to  

Euler's criterion we have for $N$ an odd prime and $a$ coprime to $N$ :  $$a^{(N-1)/2} \equiv \left(a\over N\right)\pmod{N}$$

with the Legendre symbol at the right side $\pm 1$ as claimed in our case $a=3$.
The converse is not so easy but a good start may be Lucas' theorem strengthened by Kraitchik and Lehmer (from The Prime Pages) :

Let $N>1$. If for every prime factor $q\,$ of $\;N-1$ there is an
  integer $a$ such that 
  
  
*
  
*$\displaystyle a^{N-1}\equiv 1\pmod{N},\quad$ and 
  
*$\displaystyle a^{(N-1)/q}\not\equiv 1\pmod{N}$  
  
  
  then $\; N$ is prime.

The only prime factors $q$ of $\,N-1\,$ are $2$ and $p$. If we restrict ourself to evaluation of powers of $a=3$ we get : 

if  
  
  
*
  
*$\;\displaystyle 3^{(N-1)/2}\equiv -1\pmod{N}\;$ (implying $\;3^{N-1}\equiv 1\pmod{N}$)$\quad$ and
  
*$\;\displaystyle 3^{(N-1)/p}\not\equiv 1\pmod{N}\;$
  
  
  then $N$ is prime.

Note that computations are quite efficient here since $\;(N-1)/p=2^n$ so that we could evaluate $\;r:=3^{\large{2^{n-1}}}\pmod{N}$ by squaring only and then compute $\;r^p\pmod{N}$ for the first test and $\;r^2\pmod{N}$ for the second.
This is of course weaker than your claim with the important drawback of excluding $\;\displaystyle 3^{(N-1)/2}\equiv 1\pmod{N}\;$ when $3$ is a quadratic residue modulo $N$ : that is approximately half of the interesting cases for "not too large" values of $N$! (and the minor inconvenient of adding a second test...)
A closer look shows however that $3$ will be a quadratic residue modulo $N$ only if $n=1$ or $p=3$
(I think from this result of the quadratic residue theory : $\left(3\over N\right)=+1\;$ iff $\;N\equiv \pm 1\pmod{12}\;$ without verifying all the cases I'll admit...).
The previous conditions should thus apply for all the primes $\,N =p\cdot 2^n+1\,$ with $p$ prime $>3\;$ and $n>1$.
The remaining case of prime $\,N =2\,p+1\,$ ("safe prime") was studied by Sophie Germain while the prime $\,N =3\cdot 2^n+1\,$ OEIS A039687 was studied by Golomb.
This result is incomplete but should be at least a start...
