Question: I tried implementing the Lehmann test but it doesn't work the first time round. I followed what everyone described 

1. Calculate r = [ a^( (p -1) / 2) ] mod p
2. If r is not 1 or –1 then p is definitely not a prime.
3. If r = 1 or –1 the likelihood that p is not prime is at most than 50 percent.

No matter how I did it, it never works. I even tried hard coding it

```
p = 7; //definitely a prime number

double e = (p - 1 )/2;

int f = (int)pow(3, e) % p;

cout << f <<endl;

```

and f ended up as 6

any help will be appreciated

Answer: 
By calculating `f`, you've done step 1, but you're leaving out steps 2 and 3.

```
p = 7; //definitely a prime number

double e = (p - 1 )/2;

int f = (int)pow(3, e) % p;

// Step 2
if(f % p != 1 && f % p != p - 1)
    cout << p << " is definitely not prime." << endl;
else // If not step 2, then step 3
    cout << p << " has 50% probability of being prime." << endl;

```

The operator `%` is the mod operator. It reduces the left number mod the right number. Like `10 % 8` is `2`. It's important to note that, when the left number is positive the result is always positive. So if `a = b - 1`, `a % b` is `a`, which is to say that, if `a = -1 mod b`, then `a % b == a`.

The condition `f % p != 1 && f % p != p - 1` in English is `(f % p not equal 1) AND (f % p not equal p - 1)`

One problem is that this will overflow for big `p`.

If you want to avoid using a bignum library, you can define your own pow like so:

```
unsigned int my_pow(unsigned int base, unsigned int expon, unsigned int mod){
    unsigned int result = base;
    for(int i = 1;i < expon;i++)
        result = (result * base) % mod;
    return result
}

```

You would use this like `int f = pow(3, e, p);`. I'm not sure how to bound when this will overflow, but it will be a lot larger than the normal `pow`.
f ends up as 6 because 6 is equal to -1 mod 7, hope it helps.