...heory of probabilistic primality tests (cf. [[Probabilistic primality test|Probabilistic primality test]]), as they show that Fermat's theorem, to wit $ a^p \equiv
...only if $\lambda(n) \mid n-1$. From this it follows that every Carmichael number is odd, square-free, and has at least $3$ distinct prime factors.
3 KB (485 words) - 17:34, 18 October 2014
''(on the normal number of prime factors of an integer)''
For any integer $n \ge 2$, let $\omega(n)$ denote the number of distinct prime factors of $n$. The Hardy–Ramanujan theorem [[#Referenc
4 KB (647 words) - 07:30, 18 March 2023
A result in [[probabilistic number theory]] characterising those [[additive function]]s that possess a limiting distr
...ef; Mitrinović, Dragoslav S.; Crstici, Borislav, eds. ''Handbook of number theory I''. Dordrecht: Springer-Verlag (2006). pp. 564–566. {{ISBN|1-4020-4215-9
2 KB (230 words) - 12:04, 23 November 2023
...unction $\omega(n)$, which is the number of distinct prime divisors of the number $n$, is strongly additive; and the function $\log m$ is completely additive
An arithmetic function is also called a number-theoretic function.
1 KB (206 words) - 05:52, 15 April 2023
''number-theoretic function''
...er than $x$ — describes the distribution of primes; $\pi(x,q,l)$ gives the number of primes not larger than $x$ in the arithmetic progression $p\equiv l\pmod
4 KB (608 words) - 08:18, 4 November 2023
Let $f$ be a function on the [[natural number]]s. We say that the ''normal order'' of $f$ is $g$ if for every $\epsilon
* The [[Hardy–Ramanujan theorem]]: the normal order of $\omega(n)$, the number of distinct [[prime factor]]s of $n$, is $\log\log n$;
1 KB (235 words) - 08:12, 4 November 2023
Let $f$, $g$ be functions on the [[natural number]]s. We say that $f$ has average order $g$ if the [[asymptotic equality]]
* The average order of $d(n)$, the [[number of divisors]] of $n$, is $\log n$;
1 KB (231 words) - 19:41, 17 November 2023
''of a natural number $n$''
The sum of the positive integers divisors of a natural number $n$, including $1$ and $n$:
2 KB (268 words) - 19:41, 17 November 2023
[[Number theory|number theory]] in which ideas and methods from
[[Probability theory|probability theory]] are used.
10 KB (1,718 words) - 04:55, 8 August 2018
...mber generation is possible by performing a measurement process in quantum theory.
...ision) may be potentially influenced by cosmic rays making the calculation probabilistic.
12 KB (1,954 words) - 17:47, 26 December 2013
A central technique in the probabilistic method. It is used to prove the existence of a "good" object even when th
Here, the number of events, $|I|$, may be arbitrarily large, giving the Lovász local lemma
4 KB (586 words) - 19:47, 18 December 2014
The branch of [[mathematical programming]] in which one studies the theory and methods for the solution of conditional extremal problems, given incomp
...all (or nearly all) realizations are called rigid. Restrictions are called probabilistic if discrepancies are admissible in the conditions of the problem with a pro
5 KB (768 words) - 13:11, 3 May 2016
$#C+1 = 180 : ~/encyclopedia/old_files/data/P110/P.1100230 Probabilistic metric space
...tion was introduced by K. Menger in 1942 and has since been developed by a number of authors. A treatment, comprehensive up to 1983, may be found in {{Cite|S
12 KB (1,757 words) - 08:07, 6 June 2020
The union of a finite number of sets thin at the point $ y _ {0} \in \mathbf R ^ {n} $
...]</TD> <TD valign="top"> N.S. Landkof, "Foundations of modern potential theory" , Springer (1972) (Translated from Russian)</TD></TR></table>
4 KB (696 words) - 08:25, 6 June 2020
For a given set $B\subseteq\mathbf N$ one writes $r_{B,h}(x)$ for the number of representations of the non-negative integer $x$ as a sum of $h$ terms fr
...y many positive integers $x$. See also [[#References|[a5]]] for a modified probabilistic construction which can be derandomized to yield a polynomial-time algorithm
4 KB (658 words) - 19:37, 29 March 2024
* E.D. Cashwell, C.J. Everett,. "The ring of number-theoretic functions", ''Pacific J. Math.'' '''9''' (1959) 975-985 {{ZBL|009
* Henri Cohen, "Number Theory: Volume II: Analytic and Modern Tools", Graduate Texts in Mathematics '''24
2 KB (358 words) - 17:25, 11 November 2023
...error of $a$. To characterize the error one usually states bounds on it. A number $\Delta(a)$ such that
is called a bound on the absolute error. A number $\delta(a)$ such that
3 KB (519 words) - 22:31, 1 November 2014
$#C+1 = 22 : ~/encyclopedia/old_files/data/N067/N.0607940 Number theory
...figures, were the first and the most ancient mathematical concepts. Number theory arose from problems in [[Arithmetic|arithmetic]] connected with the multipl
10 KB (1,503 words) - 08:03, 6 June 2020
The collective name for systems consisting of a large number of interconnected elements. It must be emphasized that this is an informal
...ir names, such as systems analysis, system-technology, and general systems theory, among others.
4 KB (532 words) - 17:22, 7 February 2011
Traditionally, a composite natural number $n$ is called a pseudo-prime if $2^{n-1} \equiv 1$ modulo $n$, for it has l
...ude any composite number that acts like a prime in some realization of a [[probabilistic primality test]]. That is, it satisfies some easily computable necessary, b
3 KB (516 words) - 17:58, 8 November 2014