New answers tagged number-theory
0
votes
abscissa of convergence of $\sum_{n = 1}^\infty \frac{\mu(n)}{n^s}$
I will outline how those properties can be related to each other. It is through an intermediate integral involving $M(x) = \sum_{1 \leq n \leq x} \mu(n)$.
For a sequence $\{a_n\}$ in $\mathbf C$, ...
- 39.8k
1
vote
Accepted
Countable rank discrete subgroup?
There is not even a discrete free abelian subgroup of $\mathbb{Z}_2\times\mathbb{R}$ of rank $2$. Indeed, suppose $x,y\in\mathbb{Z}_2\times\mathbb{R}$ are $\mathbb{Z}$-linearly independent. For any $...
- 317k
0
votes
For every matrix $A$ mod $r$, is there a nonzero vector $\vec x$ so that $A \vec x$ has 0 mod $r$ nonzero entries?
I will try to explain as i would do it:
Case 1: m<n
In this case, A is singular, so the statement holds trivially.
Case 2: m=n
In this case, ‖Ax⃗‖0≡‖x⃗‖0modr for all x⃗∈Zn×1r. Since n is ...
0
votes
Ramanujan's Proof of Chebycheff's Theorem
This may explain the answer to the first question:
$$\sum_{n\leq x}\sum_{p^\alpha|n}=\sum_{n\leq x}\sum_{p^\alpha\cdot m=n}=\sum_{p^\alpha m\leq x}=\sum_{m\leq x}\sum_{p^\alpha\leq\frac{x}{m}}.$$
And ...
- 1,500
0
votes
Let p be a prime number with p≡3 (mod 4) and let r be a primitive root modulo p . Prove that $\mathrm{ord}_p(-r) = (p-1)/2.$
We can write: $$(-r)^{\frac{p-1}{2}}\equiv(-1)^{\frac{p-1}{2}}r^{\frac{p-1}{2}}\mod p$$ As $p=4k+3$, $\frac{p-1}{2}$ is odd. Therefore: $$(-1)^{\frac{p-1}{2}}r^{\frac{p-1}{2}}\equiv -r^{\frac{p-1}{2}}\...
- 3,847
0
votes
Prove that sum of 2 double factorials equals to a factorial only on limited solutions
Let's prove we know all solutions. Here is an outline of a
proof strategy. Since I shall have not the time to write down the details in the near future, I hope the steps indicated are sufficiently ...
- 332
2
votes
Four squares theorem for finite fields
I am not going to give a complete answer. But it will be more than tangential you asked for.
Instead of sum of four squares we can try to find elements which are sums of two squares.
I'll indicate ...
- 19k
1
vote
Proof of the dual Möbius Inversion Formula
You've correctly recognized the one key step in all arithmetic Möbius inversion proofs: you want to recognize $\sum_{d \mid n} \mu(d)$ somewhere. Let's complete your half-proof. (The other direction ...
- 88.9k
0
votes
Accepted
Show that for an odd integer $n ≥ 5$, $5^{n-1}\binom{n}{0}-5^{n-2}\binom{n}{1}+…+\binom{n}{n-1}$ is not a prime number.
You want to show that for odd integer $n$, $ \frac{ 4^n + 1 } { 5}$ is composite.
You're on the right track, though this numerator isn't irreducible, so hint: Find the factorization.
Writing $n = 2k+1$...
- 64.4k
0
votes
What can primes (except 2,3, or 5) be congruent to (mod 30)?
maybe this is prior art that I'm unaware of, but I realized those 8 scenarios under 30
1, 7, 11, 13, 17, 19, 23, 29
for all primes can be collapsed down to a single unified formula that isn't too ...
2
votes
How is the logarithm of an integer analogous to the degree of a polynomial?
The degree of a monomial is (putting the coefficient aside) the log.
For a log, we have $\log(ab) = \log(a)+\log(b)$, and for degrees, we have $\deg(fg) = \deg(f)+\deg(g)$.
For addition, there's a ...
- 11.7k
0
votes
Use Mersenne numbers to prove that there are infinitely many prime numbers.
If $P$ were the set of all primes and were assumed to be finite $P =: \{p_1, \dots, p_k\}$, then it would have to contain $\{q_1,\dots, q_k\}$, since they are prime numbers, but all the $q_i$s are ...
- 2,245
2
votes
How is the logarithm of an integer analogous to the degree of a polynomial?
I want to expand on the comment of @math54321 and the answer of @Dietrich Burde.
If we write a non-zero natural number $n$ as $n = \sum_{j = 0}^{m} a_j 10^j$, where $a_j \in \{ 0,1,2,3,4,5,6,7,8,9 \}$ ...
- 1,793
3
votes
Accepted
Nonconstant polynomial $f(x) \in \mathbb{Z}[x]$ with $f(0)=1$, then there exists an $n \in \mathbb{N}$ such that $f(n)$ is divisible by 2021 primes.
The problem with your approach is that you need values of $p$ such that $p$ is dividing a value like $f(r)$. Even if $f(0) \equiv 1\mod p$, this in no way helps find a value $r$ such that $p$ divides $...
0
votes
Closed form expression for an integral
All series/integrals below converge absolutely, therefore a change in the order of summation/integration is justified.
By definition
$$\psi_{q}(z) + \ln(1-q) = \ln q \sum_{n = 0}^{\infty}\frac{q^{n+z}}...
- 656
1
vote
Does $(3+2\sqrt{-2})y^2=1+12\sqrt{-2}-4・17x^4$ have solution in $\Bbb{Q}_{17}$?
It's known that $\mathbb{Q}_{17}^{\times}=\mathbb{Z}\oplus\mathbb{F}_{17}^{\times}\oplus\mathbb{Z}_{17}$ . which indicates $t=x^4,\, x\in\mathbb{Q}_{17}^{\times}$ iff $val(t)\equiv 0\bmod 4$ and $t/17^...
- 664
2
votes
Unable to Understand Notations in Davenport's MNT
In the formula
$$
2\pi N(T)=\Delta_R {\rm arg} \xi(s)
$$
the term on the RHS stands for the increment of the argument of $\xi(s)$ along the boundary of the rectangle $R$, i.e., the change in the ...
- 126k
0
votes
Call $n\in\Bbb N$ "balanced" if the sum of its digits equals the count of its divisors. How many "balanced" numbers are there up to $m$?
Upto $10^9$ , we have the following values and counts :
...
- 81.1k
32
votes
How is the logarithm of an integer analogous to the degree of a polynomial?
Here's a concrete way in which they're analogous:
$\mathrm{deg}\,(f \times g) = \mathrm{deg}\,f + \mathrm{deg}\,g$
$\log |xy| = \log |x| + \log |y|$
Also: the degree of the constant zero polynomial ...
- 893
2
votes
Accepted
How to prove the p-adic expansion of negative p-adic integers ends with p-1?
See Case 1 in the proof of Theorem 3.1 here.
For a self-contained description, first look at what an infinite $p$-adic expansion is when all of its digits are $p-1$ and it starts in position $p^d$:
$$
...
- 39.8k
1
vote
Accepted
Number of Classes in a Genus of a Quadratic Form?
Watson's project of finding all genera of class number one, positive forms, was automated by Kirschmer and Lorch,. The maximum dimension is 10.
Watson proved in his 1962 Transformations paper that ...
- 136k
1
vote
Accepted
Probability for finding product?
You pick an integer $k$ and look at the product $k(k+1)(k+2)$ to see if it is divisible by $24$. Any three consecutive integers will have one integer divisible by $3$, so the real question is how many ...
- 6,845
8
votes
Accepted
How is the logarithm of an integer analogous to the degree of a polynomial?
There is a certain analogy between the ring of polynomials over a field, $k[x]$ and the ring of integers, $\mathbb{Z}$. Note that both are Euclidean domains.
Now, for a finite field, $k=\mathbb{F}_q$, ...
- 4,740
46
votes
How is the logarithm of an integer analogous to the degree of a polynomial?
Lang says that experience shows this. I only want to mention the following analogy. Writing an integer in decimal notation is like writing out a polynomial. For example,
$$
1045 = 1\cdot10^3+0\cdot10^...
- 126k
0
votes
Probability for finding product?
By "first billion natural numbers", I'm going to assume you mean all the numbers from $1$-$1,000,000,000$ (so 0 is not included). The trick here is to look at the numbers in terms of ...
- 312
1
vote
Accepted
What is $17$ adic value of $3+2\sqrt{-2}\in \Bbb{Q}_{17}$?
After knowing $\sqrt{-2}=7+a_1p+\cdots\ \ (p=17)$, we see
$$\nu_{17}(3+2\sqrt{-2})=\nu_{17}(17+2a_1p+\cdots)\geqq 1$$
and
$$\nu_{17}(3-2\sqrt{-2})=\nu_{17}(-11-2a_1p-\cdots)=0,$$
but these two numbers ...
- 2,646
0
votes
For every matrix $A$ mod $r$, is there a nonzero vector $\vec x$ so that $A \vec x$ has 0 mod $r$ nonzero entries?
So with the author's comment in OP I get to understand that it intends to prove that for any given $A\in\mathbb Z_r^{m\times n}$ with $n\ge 2$, either there is some $y\in\mathbb Z_r^n$ so that Ay=0 or ...
- 347
1
vote
Accepted
Call $n\in\Bbb N$ "balanced" if the sum of its digits equals the count of its divisors. How many "balanced" numbers are there up to $m$?
The number of divisors of some positive integer can only be determined by factoring it. But the count is routine for , say , $m\le 10^{10}$
I do not think that we can prove that there are infinite ...
- 81.1k
4
votes
Accepted
Alternating Dirichlet series involving the Möbius function.
It is indeed true. The function $(-1)^{n+1}$ is a multiplicative function (really! confirm this), and therefore the Dirichlet series can be expanded into an Euler product as usual (in its half-plane ...
- 70.9k
1
vote
How to prove the p-adic expansion of negative p-adic integers ends with p-1?
(Edit: Replaced earlier answer with different approach.)
Your expansion of $-2$ is incorrect. I would think if you see the expansions of negative numbers, you'll see what is happening. Let's take $p=5$...
- 23.8k
2
votes
Accepted
What is the decomposition of global units $1+\mathfrak{p}$?
EDIT: As clarified by the OP, the intended question is the decomposition of $U_{K, \mathfrak p} = \{x \in \mathcal O_K^\times: x \equiv 1 \pmod{\mathfrak p}\}$ instead of $1 + \mathfrak p$.
So we ...
- 21.5k
-1
votes
Proof of binomial coefficient formula.
Let $X$ be a nonempty finite set with $n$ elements. For the integer $s$ define
$$ \mathcal{P_s} (X) = \{ A \subset X \mid |A| = s\}$$
and for integer $r$ satisfying $0 \le r \lt n$ define
$$ \mathcal{...
- 11.1k
7
votes
Accepted
What's the idea of Dirichlet’s Theorem on Arithmetic Progressions proof?
The sum of the reciprocals of the primes diverges, $\sum_p\frac{1}{p}=\infty$. This can be seen using the Euler product for the Riemann zeta function (say $s>1$ real), $\zeta(s)=\prod_p\frac{1}{1-...
- 9,079
1
vote
Accepted
What are the benefits of working with smooth and admissible representations?
The group $\mathrm{GL}_n(F)$ has a topology coming from the non-archimedean topology on $F$, so you better leverage that. So (much as in the case of Lie group representations), instead of considering ...
- 12.5k
-1
votes
"The product of two prime numbers is not abundant" proof by contradiction
I don't understand the assumption in the second line. You already said they can't equal one another. If p1 equals 3 and P2 equals 2, don't you get the same results?
4/2 is less than or equal to 2.
The ...
1
vote
What is the fastest way to write an even number as the sum of two primes?
You could apply Sieve of Eratosthenes that gives primes in a range. You can sieve the range $(2, n/2)$. The sieving takes $O(n \log \log n)$ time and $O(n)$ space.
You could then test pairs of primes ...
- 2,262
0
votes
Which pairs of natural numbers $(x, y)$ satisfy $3^x = y^2 + 2$?
Elementary proof:
Knowing $x$ needs to be odd, we can write $3^x = 3 w^2$ and ask when $w$ might be a power of three, in $3 w^2 = y^2 + 2.$ This does not happen again after your initial examples, ...
- 136k
3
votes
Accepted
The set of all sums of 3 primes covers almost all of $2\Bbb{Z}+1$ (result of Helfgott), what can one say about $\Bbb{P} - \Bbb{P} = 2\Bbb{Z}$ problem?
You define a binary operation '$\star$' on $\Bbb{P}_o^2$ and claim that this defines a group operation. But it is not clear that this binary operation is even well-defined; in writing
$$[a,b]\star[c,d]...
- 60.3k
0
votes
the generators of the modular group are S and T
As I see, the problem is the induction step. Consider this
Hint: $X \in G \implies T^{a}S^{b}X \in G$
Solution:
$$
ST^mA \in G \implies T^{-m}S^{-1}(ST^mA) \in G \implies A \in G
$$
- 1,180
4
votes
Accepted
Is it true that an irreducible polynomial is only divisible by a fixed set of primes finitely many times?
Let $f \in \mathbb{Z}[x]$ be nonzero with at least two distinct complex roots (that is, $f$ is not of the form $a(x-b)^n$). Let's prove that the statement holds for $f$.
Let $S$ be a finite set of ...
- 31.7k
0
votes
Are there infinitely many $c$-th perfect powers having a constant congruence speed of $c$?
Ok, I have just found a way to prove (a generalization) of the present statement.
I am planning to write a preprint in a few of weeks, then I will be happy to share it here.
Basically, it is just a ...
- 575
3
votes
Accepted
Proof of $\inf\left \{ \frac{\mathrm{d} (n^2)}{\mathrm{d} (n)} \; \bigg| \; n \in \mathbb{N} \right \}=0$, where $d(n)$ is the sum of digits of $n$
The claim is true. Here is a solution based on this AoPS thread. Let
$$
n=10^{4k}+2\cdot10^{3k}-10^{2k}+2\cdot10^{k}+1.
$$
Then you can check that
$$
n=10^{4k}+10^{3k}+9\cdot 10^{3k-1}+9\cdot 10^{3k-2}...
- 15.3k
0
votes
Accepted
Splitting on $p$ adic unit group
To get this off the unanswered list: Except in very few exceptional cases, neither of your isomorphisms (1) nor (2) is true. I.e. those sequences, in general, do not split.
The few cases where they do ...
- 23.8k
1
vote
Is it true that an irreducible polynomial is only divisible by a fixed set of primes finitely many times?
No, see for instance $f(x)=x$ and $k=1$. Then $\{(p_1^m,m)\,:\, m\in\Bbb N\}$ is an infinite subset of said solutions.
- 1,289
1
vote
Proof of $\inf\left \{ \frac{\mathrm{d} (n^2)}{\mathrm{d} (n)} \; \bigg| \; n \in \mathbb{N} \right \}=0$, where $d(n)$ is the sum of digits of $n$
Using the letters $j$ and $n$ as shown below, it comes out
$$ d(n) = 9 \cdot 2^j - j - 4 $$
$$ d(n^2) = j^2 - j +7 $$
Getting there. I see, let us say, the ingredients of a proof allowing an ...
- 136k
1
vote
Are there infinitely many $c$-th perfect powers having a constant congruence speed of $c$?
I don't have an answer to the problem, but I've found the smallest $n$ values that satisfy the conditions for $3≤c≤32$:
...
1
vote
Algorithm for determining whether $\gcd$ of two polynomials is unequal $1$, for use in Schoof's algorithm and $ECC$
The Euclidean algorithm does not work efficiently enough here since $q$ is typically an enormous number in the context of Schoof's algorithm. The correct method is to use modular exponentiation (...
- 1,046
3
votes
Accepted
What is the simple dependence of the diagonals (or columns) of the Faulhaber matrix on the first entry (Bernoulli numbers)?
Let $a_{k,m}$ denote the coefficient of the $k$th column of $S_m$ (corresponding to the monomial $x^{m-k+2}$).
The pattern for the first column ($k=1$) is $$a_{1,m} = \left(\frac{m}{m+1}\right) a_{1,m-...
- 24.7k
1
vote
Does Euler product formula give any hints about asymptotics of primes?
Intuitively, the limit $s \to \infty$ shouldn't be expected to give asymptotic information, because the contributions from the tail of the series $\sum_{n} n^{-s}$ and $\prod_{p} \frac{1}{1 - p^{-s}}$ ...
- 126
0
votes
How many sequences satisfy this condition?
We can use exponential generating functions. To preface, we want to assign, in some form or another, a value $c_i$ to each $1 \leq i \leq N$ such that $c_i = S_j - 1$ for some $j$ and $\sum_{i = 1}^N ...
- 3,254
Top 50 recent answers are included