Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with nt.number-theory
Search options answers only
not deleted
user 7076
Prime numbers, diophantine equations, diophantine approximations, analytic or algebraic number theory, arithmetic geometry, Galois theory, transcendental number theory, continued fractions
2
votes
Accepted
Trying to solve for the remainder of $a^q$ modulo $q$
As I pointed in the comments, the equation in question for $a\not\equiv0\pmod{q}$ can be restated as
$$a + 2af_q(a) \equiv c\pmod{q},$$
where $f_q(a)$ is the Fermat quotient of $a$ with respect to $q$ …
- 29.5k
14
votes
Accepted
When is $\mathrm{gcd}(k,p^k-1)=1$ true?
It is easier to describe non-good (bad) numbers with respect to a given prime $p$. For each such number $k$, there exists a prime $q$ such that $q\mid k$ and $q\mid (p^k - 1)$. It follows that $k$ is …
- 29.5k
1
vote
Accepted
Summing the max value of the distinct pairs in a multiset
This is a corrected and extended version of my earlier comment. Let $A = \{ b_1^{m_1}, \dots, b_k^{m_k}\}$ where $b_1 < \dots < b_k$ and $m_i$ are their multiplicities with $\sum_{i=1}^k m_i = n$.
The …
- 29.5k
10
votes
Accepted
Ordinary partitions vs partitions into odd parts
The g.f. for the right-hand is
$$e^{2x}\cdot e^{2x^2} \cdots = e^{2\frac{x}{1-x}}.$$
For the left-hand side, additionally introducing variable $y$ to account for partition length, we get
$$\sum_{n\ge …
- 29.5k
0
votes
How much do these interval collections cover?
Equivalently we can define a covered number $n$ as such that there exists a prime $p<\sqrt{n}$ such that $p\nmid n$ and $\lceil n/p\rceil$ is also prime.
Indeed, taking $q:=\lceil n/p\rceil$ we have t …
- 29.5k
4
votes
Are these equations solvable in positive integers?
For (a), we can introduce $s:=x+1$ and pose the question as $(sy-1)\mid (s^4 - 3s^3 + 3s^2 - 3s + 1)$. Equivalently, we have that
$$\frac{s^2 + y^2 - 3s - 3y + 3}{sy-1}$$ is an integer. This problem i …
- 29.5k
3
votes
Accepted
Special configurations on a circle from a homological algebra problem
There is a simple characterization of interesting configurations:
Lemma. A configuration $x_0=0< x_1 < x_2 < ... <x_r$ of Gorenstein dimension $g$ is interesting if and only if there exist indices $i, …
- 29.5k
2
votes
Calculate the great common factor between $2^{2n+1}-1$ and $2^{4m+2}+1$
In general we have
$$\gcd(2^a + 1, 2^b - 1) = \frac{2^{\gcd(2a,b)}-1}{2^{\gcd(a,b)}-1},$$
which is evaluates to $1$ for $a=4m+2$ and $b=2n+1$.
- 29.5k
9
votes
Does $a_0=6$, $a_{n+1} = (a_n-1)\cdot a_n\cdot (a_n+1)$ define a square-free sequence?
The question is equivalent to asking whether $b(n):=\frac{a(n)}{a(n-1)}$ are squarefree. The sequence $b(n)$ is listed in OEIS A231831 and satisfies the recurrence $b(n+1) = b(n)^3 + b(n)^2 - 1$ with …
- 29.5k
2
votes
Accepted
The existence of solutions of a system of indeterminate equations
In the comments OP proposed a greedy algorithm to represent a given positive integer $A$ as the sum of triangular numbers whose indices sum to $m$, and applied it to $A = \frac{m(m+1)}4$. I will prove …
- 29.5k
1
vote
The existence of solutions of a system of indeterminate equations
I expect that in many cases the following construction will do the job. By Fermat polygonal number theorem, we have representation of $\frac{m(m-3)}4$ as the sum of 3 triangular numbers:
$$ \frac{m(m- …
- 29.5k
30
votes
Proof for new deterministic primality test
The claim does not hold. A counterexample is given by $n=14$, $p=134123250258009499$ and correspondingly
$$N = 2197475332227227631617 = 193 \cdot 12289 \cdot 926510094425921.$$
It can be easily verifi …
- 29.5k
2
votes
Accepted
Coefficients of number of the same terms which are arising from iterations based on binary e...
In other words, if $(b_\ell b_{\ell-1}\dots b_0)_2$ is the binary representation of $n$, then
$$a(n) = g(g(\dots g(g(0,b_0),b_1)\dots ),b_{\ell-1}), b_\ell),$$
where
$$g(A,b) = \begin{cases} A+2, &\te …
- 29.5k
1
vote
Solutions of a linear diophantine equation
$N(h)$ can be expressed via partition function $q$ as $$N(h)=q(6h-6,h-1).$$
- 29.5k
1
vote
Algorithm for finding integers in a range with multiples in a short interval
Depending on the value of $D$ as compared to $X$, you may want to switch from scanning the interval $[D+1,2D]$ to the interval of co-factors: $\big[ \lceil \frac{X}{2D} \rceil, \lfloor \frac{X+H}{D+1} …
- 29.5k
3
votes
Accepted
Lucas–Lehmer test and triangle of coefficients of Chebyshev's
By the composition property of Chebyshev polynomials $T_m(T_n(x))=T_{mn}(x)$. Since $x^2-2 = 2T_2(\tfrac{x}2)$, we have $S_i = 2T_{2^i}(2)$ for all $i\geq 0$.
Furthermore, since $T_{2^k}(x) = \frac{U_ …
- 29.5k
4
votes
Non-Wieferich primes with Euler quotient modulo $p$ two and alternating harmonic numbers
While no composite terms of A128465 are known, here is a proof that an odd prime $p$ belongs to A128465 if and only if $b(p)\equiv 2(-1)^{\tfrac{p+1}2}\pmod{p}$.
First notice that for an odd prime $p$ …
- 29.5k
1
vote
Accepted
Asymptotic for a sum involving GCD and Euler totient function
Let $c:=\gcd(\phi(d),d)$. then setting $r:=dk$ the sum can be rewritten as
$$c\sum_{k\leq x/d} \gcd(\tfrac{\phi(d)}c,k) \approx \frac{c^2x}{d\phi(d)}f(\tfrac{\phi(d)}c),$$
where $f(m) := \sum_{k=1}^m …
- 29.5k
3
votes
How many ways to pick k integers with fixed sum and product
Let $B_k({\cal S},{\cal P},{\cal X})$ be a bound for the number of solutions for any $S\leq {\cal S}$, $P\leq {\cal P}$ and ${\cal X} \leq x_1 \leq x_2 \leq \dots \leq x_k$.
Using Iverson's bracket no …
- 29.5k
3
votes
Accepted
Counting numerical semigroups by largest element of minimal generating set
A key observation is that two sets of generators $g, g'\subseteq [n]$ produce the same semigroup if and only if $\langle g\rangle \cap [n] = \langle g'\rangle \cap [n]$. Hence, the number of different …
- 29.5k
3
votes
Accepted
A query about modular arithmetic on a matrix
The question is equivalent to finding an integer vector $x$ such that
$$xM = \iota_K,$$
where $\iota_k$ is the all-1 vector of length $K$.
By Rouché–Capelli theorem, this equation has a solution modul …
- 29.5k
2
votes
Accepted
Partition of $(2^{n+1}+1)2^{2^{n-1}+n-1}-1$ into parts with binary weight equals $2^{n-1}+n$
Notice that for $i\in\{0,1,\dots,2^{n-1}+n\}$ we have
$$a(i+1,2^{n-1}+n) = 2^{2^{n-1}+n+1} - 1 - 2^{2^{n-1}+n-i}.$$
Then the sum in question can be easily computed:
\begin{split}
& a(1,2^{n-1}+n)+\sum …
- 29.5k
3
votes
Only trivial solutions to system of linear diophantine equations possibly related to hamilto...
Below I show that $m$ cannot be constant.
The given system of $m$ equations can be reduced to the case of $m=1$, that is, to a single equation:
$$\sum_{j=1}^n y_j a'_{j} = \sum_{j=1}^n a'_{j}$$
where …
- 29.5k
2
votes
Existence of solution for a system of quadratic diophantine equations / symmetric quadratic ...
UPDATE. Using factorization $-2(x+1)^2x^{p-3}$ over the corresponding number field, I established that there are no solutions for $p=17$. Furthermore, I computationally verified that for primes $p<30$ …
- 29.5k
3
votes
Accepted
A diophantine equation inspired in a conjecture due to Gica and Luca, example of a large Mer...
The equation (1) for a fixed $x$ is equivalent to the congruence:
$$y^2 \equiv 2(1+z^2)\pmod{x}.$$
For $x=25964951$, we have $2\equiv 3328351^2\pmod{x}$, and thus all solutions are obtained from those …
- 29.5k
7
votes
Accepted
Small covering of divisors
UPDATED
We can simply take
$$B = \{1\} \cup \{ d\in D_n\ :\ d > n^{1/2} \}.$$
Then for any $d\in D_n$:
if $d\leq n^{1/2}$, we take $(a,b)=(d,1)$;
if $d>n^{1/2}$, we take $(a,b)=(1,d)$.
Then
$$\sum_{ …
- 29.5k
10
votes
Primality test for numbers of the form $\frac{a^p-1}{a-1}$?
The test fails already for $p=3$ and $a=7$, claiming that $57=3\cdot 19$ is prime.
ADDED. And new test fails for $a=10$ and $p=5$.
ADDED#2. And the test in EDIT 2 fails for $a=52$ and $p=3$.
- 29.5k
5
votes
Primality test for $\frac{(10 \cdot 2^n)^m-1}{10 \cdot 2^n-1} - 2$ and $\frac{(10 \cdot 2^n)...
It's often the case with such tests that the "only if" part is more or less easy to prove, while the "if" part is inaccessible for proving or disproving. Below I prove the "only if" part, ie. assuming …
- 29.5k
6
votes
Resources where I can find open problems in number theory along with their level of difficulty
Some open problem collections from my bookmarks:
Number Theory @ Open Problem Garden
List of unsolved problems in number theory @ Wikipedia
Unsolved problems @ MathWorld
Unsolved Problems and Rewards …
5
votes
Parametrization of integral solutions of $3x^2+3y^2+z^2=t^2$ and rational solutions of $3a^2...
For #1, we can take a particular solution such as $(a_0,b_0,c_0)=(0,0,1)$, and search parametric solution in the form: $(a,b,c)=(a_0+\alpha t, b_0+\beta t, c_0+t)$. Plugging it into the equation and s …
- 29.5k
5
votes
Accepted
Sequences that sums up to second differences of Bell and Catalan numbers
Let me address the case of $s_2(n)$.
First we notice that $g(n-1) = k$ whenever $n=(2k+1)2^t$. Then
for $n=2^{t_1}(1+2^{1+t_2}(1+\dots(1+2^{1+t_\ell}))\dots)>1$ with $t_j\geq 0$, we have
$$a_2(n) = \b …
- 29.5k
3
votes
Accepted
Constructing an integer with small residues for two distinct primes in polynomial time
If such $m$ exists, then $m=up+a=vq+b$ for some $u,v\in O(T^{1/2+\epsilon})$ and $a,b\in O(\mathrm{polylog}(T))$. Then $up-vq=b-a$ and thus $\frac{p}q - \frac{v}u=\frac{b-a}{uq}$, implying that $\frac …
- 29.5k
6
votes
Accepted
On roots of irreducible quadratics modulo composites
Ability to find all roots leads to finding factorization of $N$. For example, if $N=pq$ is a product of two odd primes, and we find a root $x'$ of $x^2-1\equiv 0\pmod N$ such that $x'\equiv 1\pmod p$ …
- 29.5k
0
votes
Accepted
Is there a general way to solve this modular equation?
There seems to be no simple formula for the solutions to the given congruence. Still, they can be computed iteratively as follows.
First, we notice that $2^m = (3-1)^m \equiv (-1)^m \sum_{i=0}^{N-1} \ …
- 29.5k
1
vote
A variant of Landau's function
Let $k = \nu_2(g(n))$. Then $g(n)$ is attained at $n = 2^k + \texttt{1s and powers of odd primes}$, implying that $g(n) = h(n-2^k)2^k$.
Hence, $h(n) = \frac{g(n+2^k)}{2^k}$ for some $k$ satisfying $k= …
- 29.5k
3
votes
Complexity of a Fibonacci numbers discrete log variation
The Binet formula for Fibonacci numbers is
$$F_n = \frac{\phi^n - (-\phi)^{-n}}{\phi - (-\phi)^{-1}},\qquad\text{where}\ \phi:=\frac{1+\sqrt{5}}2.$$
Then the congruence $F_n\equiv k\pmod{m}$ reduces t …
- 29.5k
5
votes
Accepted
Number of positive integers $k$ such that there exists a nonnegative integer $m$ with $k + k...
The formula $c(n)=a(n+1)$ is pretty much straightforward, noticing that
$$\lfloor \log_{i+1}(n-i)\rfloor - \lfloor\log_{i+1}(n-1-i)\rfloor=1\quad\text{iff}\quad n-i=(i+1)^m\text{ for some }m.$$
The l …
- 29.5k
4
votes
Accepted
direct proof of an identity regarding certain symmetry of integer partitions?
I assume you meant $j_t\leq a_t$ (not $j_t<a_t$).
It's sufficient to prove that for any analytic function $f(x)$, the function
$$F(a_1,a_2) := \sum_{l\geq 0} \sum_{j=0}^{a_2} \frac{(-1)^ll!}{(a_1+l+1) …
- 29.5k
9
votes
$23005\cdot (2^n-1)\cdot 2^n +1=p^2$
Multiplying the equation by $2^n$ and denoting $X:=2^n$ and $Y:=p2^{\lfloor n/2\rfloor}$, we obtain two elliptic curves (depending on the parity of $n$):
$$(23005(X-1)X+1)X=Y^2,$$
$$(23005(X-1)X+1)X=2 …
- 29.5k
3
votes
Accepted
Least modulus distinguishing some integers
I'm not sure about the state of art, but here is a rough estimate in terms of $c$ and $\ell:=a_c-a_1$ in the case $c\ll \ell$.
First, we notice that for an integer $M$ satisfying
$$M\# ~>~ \big(\frac{ …
- 29.5k
3
votes
Accepted
Runs of consecutive numbers all of which are Murthy numbers
Let $m+1, \dots, m+n$ be a sequence of $n$ consecutive Murthy numbers such that each $m+i$ shares with its reversal $\overline{m+i}$ a prime factor $p_i\equiv 3\pmod4$ such that 10 is a quadratic nonr …
- 29.5k
3
votes
What is the highest power of 2 that divides $3^y(2z-1)-1$?
I doubt there is a simple expression for $x$ as a function of $y,z$. However, it is possible to characterize all cases when $2^k\mid 3^y (2z-1) - 1$ for a given positive integer $k$.
Say, for $k\geq 3 …
- 29.5k
23
votes
Accepted
Are there infinitely many positive integer solutions to $(3+3k+l)^2=m\,(k\,l-k^3-1)$?
It does have infinitely many positive solutions. Here is just one such series.
Consider the following recurrence sequence:
$$u_0=1,\ u_1=2,\ u_{n+1} = 23 u_n - u_{n-1} - 4\qquad (n\geq 1).$$
Let $t,k$ …
- 29.5k
6
votes
Convergence of $\sum(n^p\sin^qn)^{-1}$
A while ago I've addressed this question in On convergence of the Flint Hills series.
- 29.5k
5
votes
Accepted
Analogue of Fermat's little theorem for Bernoulli numbers
A proof is essentially given in Section 5.1 of Notes on primitive lambda-roots by P. J. Cameron and D. A. Preece.
- 29.5k
7
votes
For which $n$ is $\sum_{k=1}^n 1 / \varphi(k)$ an integer?
Here is some computational evidence that $n\in\{1,2,4\}$ are the only $n$ that deliver an integer sum.
For an odd prime $p$, let $a_p < b_p$ denote two smallest even positive integers such that $a_pp+ …
- 29.5k
17
votes
When do binomial coefficients sum to a power of 2?
This is a follow-up to John's answer.
Here is the questionable "theorem" from the 2nd (2013) edition of Erickson's book (thanks @spin for the pointer), which in the 1st (1996) edition was numbered as …
- 29.5k
24
votes
When do binomial coefficients sum to a power of 2?
I doubt this problem has an easy solution. It is clear how it was approached for small fixed $N$. Below I show how it can be addressed for the case of fixed odd $n>1$.
When $n>1$ is odd, $S(N,n)$ as a …
- 29.5k
3
votes
Accepted
Relation between $\sum_{k\ge 0}\binom {n+k}{k}a_k $ and $\sum_{k\ge 0}\binom {n+k}{k}\frac{a...
Since the second sum cannot start at $k=0$, I assume that both sums start at $k=1$.
Consider a particular example: $a_k = k\alpha^k$ with $|\alpha|<1$. Then
$$\sum_{k\geq 1} \binom{n+k}k \frac{a_k}k = …
- 29.5k
4
votes
Accepted
What work can be done to study the solutions of $\varphi\left(x^{\sigma(x)}\sigma(x)^x\right...
Here is a proof that if an odd integer $x>1$ satisfies (1), then $x$ is a perfect number.
First, by using the property that $\varphi(nm)=n\varphi(m)$ whenever $\mathrm{rad}(n)\mid\mathrm{rad}(m)$, we …
- 29.5k