# Questions tagged [algorithms]

Mathematical questions about Algorithms, including the analysis of algorithms, combinatorial algorithms, proofs of correctness, invariants, and semantic analyses. See also (computational-mathematics) and (computational-complexity).

1,000 questions
Filter by
Sorted by
Tagged with
35k views

### How to use the Extended Euclidean Algorithm manually?

I've only found a recursive algorithm of the extended Euclidean algorithm. I'd like to know how to use it by hand. Any idea?
• 2,307
21k views

### Split $n$ into nontrivial factors via a nontrivial square-root of $1\!\pmod{\!n}$

Coming from an understanding of Fermat's primality test, I'm looking for a clear explanation of the Miller-Rabin primality test. Specifically: I understand that for some reason, having non-trivial ...
• 465
17k views

### Efficiently finding two squares which sum to a prime

The web is littered with any number of pages (example) giving an existence and uniqueness proof that a pair of squares can be found summing to primes congruent to 1 mod 4 (and also that there are no ...
• 704
23k views

### How to integrate $\int \frac{x}{\sqrt{x^4+10x^2-96x-71}}dx$?

I read about $\int \dfrac{x}{\sqrt{x^4+10x^2-96x-71}}dx$ on the Wikipedia Risch algorithm page. They gave an answer but I don't understand how they got it.
• 1,748
9k views

### A natural number multiplied by some integer results in a number with only ones and zeros

I recently solved a problem, which says that, A positive integer can be multiplied with another integer resulting in a positive integer that is composed only of one and zero as digits. How can I ...
2k views

I input ...
• 15.9k
2k views

• 1,727
143k views

### How to solve this recurrence $T(n) = 2T(n/2) + n\log n$

How can I solve the recurrence relation $T(n) = 2T(n/2) + n\log n$? It almost matches the Master Theorem except for the $n\log n$ part.
• 753