Lucas pseudoprime checker
Spot the odd composites that fool the Lucas test: with P equal to 1 and Q equal to −1, the composite 323 still passes, making it the smallest Fibonacci pseudoprime. The result also shows D, the Jacobi symbol and the index checked. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- N
- 323
- P
- 1
- Q
- -1
- D
- 5
- Jacobi
- -1
- U index
- 324
- U mod n
- 0
A Lucas pseudoprime is an odd composite integer that still satisfies the same Lucas U-sequence congruence that every prime must obey for given parameters P and Q. Cryptographers, number-theory students, and primality-test implementers use this check to separate honest primes from composites that fool a single Lucas layer—exactly the failure mode the Baillie–PSW family is designed to catch when combined with a strong Fermat test.
What a Lucas pseudoprime is and how the U-test works
Lucas sequences U_k(P, Q) and V_k(P, Q) are the integer recurrences defined by U_0 equals zero, U_1 equals one, V_0 equals two, V_1 equals P, and the common linear step X_k equals P times X_{k-1} minus Q times X_{k-2}. Their characteristic discriminant is D equals P squared minus four Q. For an odd integer n greater than one that is coprime to Q times D, let epsilon be the Jacobi symbol of D over n, which is either plus one or minus one.
Every odd prime p that satisfies the coprimality condition obeys U_{p minus epsilon} congruent to zero modulo p. A positive odd composite n that still satisfies the same congruence is called a Lucas pseudoprime with parameters P and Q. The classical Fibonacci case uses P equals one and Q equals negative one, so U_k is the Fibonacci sequence and D equals five; the smallest Fibonacci pseudoprime is three hundred twenty-three.
Stronger variants (extra-strong Lucas, Frobenius) add conditions on V, but this capability implements the standard U-only definition used in textbooks and research notes on Lucas pseudoprimes of special types. Knowing whether a candidate is merely a probable prime or a true pseudoprime helps you decide whether a single Lucas layer is enough for your risk budget or whether you must stack it with a strong base-two test as in Baillie–PSW.
FAQ
What is a Lucas pseudoprime with parameters P and Q?
An odd composite n coprime to Q·D (D=P²−4Q) such that U_{n−(D/n)}(P,Q) ≡ 0 (mod n), where (D/n) is the Jacobi symbol. Primes that pass the same test are not called pseudoprimes.
Why does the checker reject a perfect-square discriminant?
When D = P² − 4Q is a non-negative perfect square the Lucas sequences degenerate and the primality congruence is not meaningful.
Is 323 a Lucas pseudoprime?
Yes. With P equal to 1 and Q equal to −1, the Fibonacci case, D is 5, the Jacobi symbol is −1 and U at index 324 is divisible by 323. Since 323 is composite, it is a Lucas pseudoprime, the smallest Fibonacci one.
What happens if I test a real prime such as 13?
It passes the Lucas test but is not labelled a pseudoprime, because a pseudoprime has to be composite. The result tells you separately whether the congruence holds and whether the number is composite.
Is the Lucas test alone enough to prove a number is prime?
No. Some composites pass a single Lucas layer, which is why the Baillie–PSW approach pairs it with a strong Fermat test in base 2. This check shows you whether your candidate is one of those composites.
Related tools
For developers — API access
Everything on this page is available programmatically. This section is for teams who want to wire it into their own systems; everyone else can just use the tool above.
API endpoint
Prefer to automate it? One authenticated POST creates the task; the result comes back by webhook or a signed link. The same capability also runs here on the web, by email and from Telegram — and soon from our app too.
Call it from your stack
curl -X POST https://api.kit.forhosting.com/numth/lucas-pseudoprime-check \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":"323","P":"1","Q":"-1"}'const res = await fetch("https://api.kit.forhosting.com/numth/lucas-pseudoprime-check", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": "323",
"P": "1",
"Q": "-1"
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/lucas-pseudoprime-check",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": "323",
"P": "1",
"Q": "-1"
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/lucas-pseudoprime-check", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":"323","P":"1","Q":"-1"}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":"323","P":"1","Q":"-1"}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/lucas-pseudoprime-check", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Example request
{
"n": "323",
"P": "1",
"Q": "-1"
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.lucas_pseudoprime_check",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}The API is asynchronous: the call returns a task_id immediately and the result arrives by webhook. Polling is capped at 1 req/s per task.
Pricing
Published price — no tokens, no invented credits. A failed task is never charged.
Errors
| HTTP | Code | Meaning |
|---|---|---|
401 | unauthorized | Missing or invalid API key. |
402 | insufficient_balance | Your balance doesn't cover the task price. |
404 | unknown_type | That task type doesn't exist. |
429 | rate_limited | Too many requests. Use the webhook instead of polling. |
Technical notes
This Lucas pseudoprime checker accepts n together with P and Q, builds the discriminant D equals P squared minus four Q, rejects the request when D is a perfect square, computes the Jacobi symbol of D over n, evaluates U at index n minus that symbol modulo n with a binary doubling ladder, and reports both whether the congruence holds and whether n is composite.
What a Lucas pseudoprime is and how the U-test works
When D is a non-zero perfect square the Binet-style closed form collapses to a pure geometric progression and the sequences lose the arithmetic properties that make them useful for primality tests, so this endpoint refuses those parameters with invalid_input rather than returning a meaningless zero.
Input contract, response fields, and error behaviour
A genuine prime such as thirteen with the same parameters passes the Lucas test but is not labelled a pseudoprime. POST a JSON body with three required integer fields: n, the odd candidate at least three; P, the first Lucas parameter; and Q, the second. Each field may arrive as a JSON number or as a decimal integer string. Non-integers, missing fields, even n, and n below three fail with invalid_input naming the problem. On success the body echoes n, P, Q, and D as decimal strings; jacobi is the Jacobi symbol of D over n as a number in the set minus one, zero, or one; u_index is n minus jacobi when the symbol is non-zero; u_mod_n is U at that index reduced modulo n; gcd_ok is true when n is coprime to Q times D; passes_lucas_test is true exactly when the U-congruence holds under the classical conditions; is_prime is a deterministic Miller–Rabin verdict in the supported range; and is_lucas_pseudoprime is true only when n is composite, gcd_ok holds, the Jacobi symbol is non-zero, and the congruence still holds. The method field is always the string lucas_u_sequence so clients can pin the algorithm in logs. Example: n equals three hundred twenty-three, P equals one, Q equals negative one yields D equals five, jacobi equals minus one, u_index equals three hundred twenty-four, u_mod_n equals zero, is_prime false, and is_lucas_pseudoprime true. Failed validation is not billed; successful calls cost the published $0.002 base price on the API path.
Where a Lucas pseudoprime API earns its keep
Classroom and contest platforms need a deterministic oracle that marks Fibonacci and general Lucas pseudoprimes correctly without students hand-rolling modular recurrence code that overflows sixty-four-bit integers. Library authors who ship Baillie–PSW or pure Lucas layers use a known-good checker to regression-test their U_k ladder against famous composites such as three hundred twenty-three before they claim zero known counterexamples. Content sites that rank for lucas pseudoprime checker gain a live tool whose free browser path matches the paid automation path on the same pure module. Cryptography courseware can demonstrate that a single algebraic test is not a primality certificate by showing a composite that still returns passes_lucas_test true while is_prime is false. Research notebooks that scan parameter families for new Lucas pseudoprimes of special types benefit from a tiny parse API that returns the full intermediate state—D, Jacobi, index, and residue—so they can filter and plot without re-implementing quadratic reciprocity.
Integration use cases
Classroom Fibonacci and Lucas PSP drills
Let students submit n with P=1, Q=−1 (or other parameters) and verify is_lucas_pseudoprime against textbook lists such as 323.
Primality-library regression tests
Pin known Lucas pseudoprimes and primes in CI so your U_k modular ladder never drifts from the classical congruence.
Research parameter sweeps
Scan families of P and Q for composite n that still satisfy U_{n−ε} ≡ 0 (mod n), using D, jacobi, and u_mod_n in the response.
Technical questions
Is 323 a Lucas pseudoprime?
Yes for the Fibonacci parameters P=1, Q=−1 (D=5). It is composite (17×19) yet U_{324} ≡ 0 (mod 323), so is_lucas_pseudoprime is true.
Does a true prime count as a Lucas pseudoprime?
No. True primes that satisfy the U-congruence set passes_lucas_test to true and is_prime to true, but is_lucas_pseudoprime remains false by definition.
What does the Lucas pseudoprime checker cost?
The browser tool is free. API requests use prepaid KIT balance at $0.002 per successful call; invalid input is not billed.