New answers tagged number-theory
0
votes
I find some patterns when analyzing the number of ways to represent an even number as sum of odd primes
It is not really an answer, but a big comment.
I have download your file output.txt, and provided some analyzes.
I will denote :
$g_2(2n) = $ the number obtained with your process (number of primes ...
- 1,563
0
votes
Accepted
Euler's Totient function
I have got the answer for this question. Thank you for the clarification in the comments. I have been trying to check for the numbers of the form $X = 2^a.5^b$ and $X = 2^a.5^b.p_1.p_2...p_k$ but I ...
- 129
0
votes
Primitive polynomial for non-prime $\mathbb{F}_q$
If $q$ is not too large, there is a simple series of tests. Find all the prime factors of $q-1$, and then raise a candidate primitive element to all combinations of those prime factors except all of ...
- 669
0
votes
How far away is a number from being a power?
You can trivially calculate the 2nd, 3rd, 4th etc root of n, rounded to the nearest integer. And you don't need k-th roots where k is composite, saving quite a lot of work. For small n, say n ≤ 10^10, ...
- 10.3k
7
votes
How far away is a number from being a power?
The distance from $n$ to the nearest $k$th power of an integer is exactly $\min\{ n-\lfloor m^{1/k}\rfloor^k,\lceil m^{1/k}\rceil^k - n \}$. Therefore if $n\le2^B$, the distance from $n$ to the ...
- 86.9k
2
votes
Primitive polynomial for non-prime $\mathbb{F}_q$
Short answer: if we can factor polynomials over non-prime fields, then we can find primitive polynomials for them using primitive polynomials for prime fields.
Let $q=p^k$; we want to find a primitive ...
- 86.9k
1
vote
About prime numbers (Goldbach) and a periodic integer sequence
Prof. Carl Pomerance has just provided the answer:
"Well the statement of your theorem presumes that Goldbach has
been proved. Here's a version that does not make this presumption:
If $2N = p+q$,...
1
vote
Recovering irrational number $\alpha$ from behavior of the sequence $ (\{ m\alpha \})_{m \geq 1}$
$\varphi$ and its square $\varphi + 1$ are both Pisot numbers and quadratic integers, so their sequences are identical. This already gives a counter-example on the question relating to determining ...
- 156
1
vote
Accepted
Counting "lattices" on a circle
As $\mathbb{Z}[\omega]$ is a Euclidean domain, hence it is a PID and UFD. We can see that the diagram below commutes:
$$
\require{AMScd}
\begin{CD}
\mathbb{Z}[x] @>\text{kill }p>> \...
- 436
0
votes
Closed form expression of coefficients of rational function
I assume the exponents $e_j$ are distinct positive integers, of which $e_s$ is the largest.
Let $p(x) = 1 - c_1 x^{e_1} - \ldots - c_s x^e_s$. Being a polynomial, it can be factored as $\prod_{j=1}^{...
- 463k
2
votes
Show that $\sum_{n \leq x} \left( \frac{\phi(n)}{n} \right)^\kappa = c(\kappa)x + O(x^\epsilon)$.
Following Conrad's hint, we observe that for $s$ with sufficiently large real part,
$$
\sum_{n} \phi^{\kappa}(n) n^{-s-\kappa} = \prod_{p}\left(1+\sum_{m} p^{(m-1)\kappa}(p-1)^{\kappa} p^{-m(s+\kappa)}...
- 727
0
votes
Ignoring units in unique factorization and divisibility theory
It might be worth pointing out that if $R$ is a commutative ring and $p \in R$ is a prime element, then if $Rp$ denotes the prime ideal generated by $p$, the generators of $Rp$ are exactly the ...
- 6,612
7
votes
Recovering irrational number $\alpha$ from behavior of the sequence $ (\{ m\alpha \})_{m \geq 1}$
This is related to the three gaps theorem, which gives the values of the lengthes of the intervals of $[0,1]$ defined by $c_1,\ldots,c_n$. There are at most three different lengthes, which can be ...
- 8,853
1
vote
2
votes
Doubt regarding the prime counting function $\pi(n)$
You may use the bounds $\frac{x}{\log x}\lt \pi(x)\lt \frac{3x}{2\log x}$ for $x\geq 17$. It follows $\pi(n^2)-\pi\left(\left\lfloor \frac{n^2}{2}\right\rfloor\right) \gt \frac{n^2}{2\log n} - \frac{...
- 4,463
1
vote
Is there an irrational number $\alpha$ such that the max value of $(\{m\alpha\})_{m\geq 1}$ is never an integer multiple of that sequence's min value?
If $c_p=kc_q$ for some integer $k$ we have $p\alpha=kq\alpha+r$ for $p,q,r,k$ integers or $\alpha=\frac r{p-kq}$ which cannot be the case if $\alpha$ is irrational unless $p=kq$ and $r=0$. The last ...
- 380k
-1
votes
Prove that $\prod_{i<j} (p_i^{p_j}-p_j^{p_i})$ is divisible by $5777$
Here's my attempt to attack this problem.
$5777=53\times109$ and for $5777$ to divide the given product either each of 53 and 109 will divide a term each or both will divide a single term in the ...
3
votes
Elliptic Curves over finite field which contains Klein's-4 Group as a subgroup
There is only one point at infinity on the curve, namely the point $(0,1,0)$ which serves as the identity element for the group of rational points. All other points are finite and may be expressed as ...
- 500
3
votes
Elliptic Curves over finite field which contains Klein's-4 Group as a subgroup
Hint. If I'm not mistaken, for an elliptic curve in the form $y^2=x^3+ax+b$
then $−(x,y)=(x,−y).$
Hence if a point $P=(x,y)$ satisfies $2P=0$, then $y=0$
or $y=\infty$.
Note that you need to check in ...
- 15.7k
0
votes
I find some patterns when analyzing the number of ways to represent an even number as sum of odd primes
The prime number theorem says approximately that the probability that a random integer $n$ is prime is about $1/\log n$ on average. Consider an even integer $m$. Then we might expect that the number ...
- 93.5k
1
vote
Accepted
Conjecture: If $n$ is an odd positive integer then $\gcd\left(2^{n}+5,5^{n}-3^{n}\right)=1$.
Let $n_0$ be an odd integer such that $n_0 \geq 3$.
Since $\gcd(5, 3) = 1$, by Zsigmondy’s theorem, $5^{n_0} - 3^{n_0}$ has a primitive prime divisor $p$.
In particular, $p$ is odd (since $p$ does ...
- 148
1
vote
Accepted
For which integer n, is there a circle inscribing n gridpoints
I'll do my best to explain the solution given on the link you referenced. The first step is to consider the set $S$ of all lines that are perpendicular bisectors to $2$ integer points. The main ...
- 1,343
4
votes
Accepted
On Theorem 2.7 of Montgomery and Vaughan's MNT
Without loss of generality, we can assume that $\delta\in\left(0,\log\left(2\right)\right)$ since, if I remember correctly, in that theorem we want to take $\delta\rightarrow0^{+}$. Then $$\int_{1}^{2}...
- 33k
2
votes
Accepted
Computing primes of the form $x^2+ny^2$
Let's start with $n$ odd.
Alright, you want even discriminant $-4n$ First you find, using an algorithm due to Cornacchia, or one due to Tonelli-Shanks, a solution $\beta$ to
$$ \beta^2 \equiv ...
- 143k
3
votes
A regular polygon of $2023$ sides is inscribed in a circle of unit radius. Prove that its side and all its diagonals have irrational lengths
An elementary solution:
Create an isosceles triangle by drawing two radii from the center of the circle to the ends of the side/diagonal; the vertex angle $\theta$ is some integer multiple of $2\pi/...
- 2,296
6
votes
A regular polygon of $2023$ sides is inscribed in a circle of unit radius. Prove that its side and all its diagonals have irrational lengths
Any side or diagonal length of a regular $2023$ sided polygon can be represented as $|w-1|$ where $w$ is a $2023$th root of unity other than $1$.
Suppose $|w-1| = q\in\mathbb Q$. We have
$$\begin{...
- 5,643
0
votes
Question on relationship between OEIS entries A020498 and A172407
Say that two sets $S$, $T$ of $n$ integers each have the same shape if there is some $k$ where $T=\{s+k: s\in S\}$.
An admissible $n$-tuple is a set $S$ of $n$ integers such that there are infinitely ...
- 3,041
6
votes
Accepted
A regular polygon of $2023$ sides is inscribed in a circle of unit radius. Prove that its side and all its diagonals have irrational lengths
Let $P$ be a regular polygon with $2023$ sides whose vertices lie on the unit circle. We can think of $P$ as being drawn in the complex plane. Without loss of generality, we may assume $V_k = e^{2\pi ...
- 2,769
0
votes
Is it known that all primes can be expressed as a square number minus a prime number?
Comment: I found this in a book which can help to formulate the matter.
Problem: Prove that any number $n>6$ can be expressed as the sum of two numbers prime to each other.
Solution:
case 1: the ...
- 11.6k
2
votes
Accepted
Action of $SL_2(F)$ on Heisenberg group and Weil representation
This is too long for a comment, but may be it works as an answer. I believe that the formula
$$
g\cdot(v^*,v,t) = \left( av^*+bv,cv^*+dv,t\frac{\psi(-B(av^*+bv,cv^*+dv))}{\psi(-B(v,v^*))} \right)
$$
...
- 3,367
1
vote
Factoring semiprimes via sum of two squares?
To answer question 2 (question 1 has been dispatched in the comments), all the odd semiprimes are in $D$, and the even semiprimes have zero density in the set of all semiprimes, so the required ...
- 183k
-1
votes
Divisibility by $33^{33}$
My approach to this problem was quite simple. I found for which values of $k$ is $19^k+92^k$ divisible by $3$,$11$ or $33$.
I found out that:
$3 \mid 19^k+92^k$ when $k$ is odd, and $3^2|19^k+92^k$ ...
0
votes
Can you do modulos with irrational numbers?
You can define such an equivalence relation on real numbers by stating that $x\equiv y\bmod p$ if and only if $x-y\in \mathbb{Z}$ and $p\vert x-y$. You can check that this satisfies all the properties ...
- 2,160
17
votes
Is it known that all primes can be expressed as a square number minus a prime number?
This seems to be unknown, and like many problems of this form, hard to approach. Indeed, in this case even if it was not true for some particular prime $p^*$, how would you even prove that $n^2-p^*$ ...
- 43.5k
7
votes
Sum of class numbers
Next morning, guess I should throw in some examples of binary quadratic forms and the form class number. To save typing, I will use the notation $<a,b,c>$ to refer to the binary quadratic form
...
- 143k
6
votes
Accepted
Sum of class numbers
Actually, I came up with an answer myself which I will post hier in case anyone else will encounter the same problem in future:
The result which is applicable here is Corollary 7.28 of the every now ...
- 1,173
2
votes
Class numbers of $\mathbb{Z}[\sqrt{-p}]$, $h(-p)$ and $h(-4p)$
We certainly can define a ring with characteristic discriminant $-28$, and that would be $\mathbb{Z}[\sqrt{-7}]$ whose minimal associated polynomial equation is $x^2+7=0$.
Like all $\mathbb{Z}[\sqrt{-...
- 44k
4
votes
Accepted
Nim-like game from Swedish math competition
This is an example of a subtraction game with a finite subtraction set (played according to the normal play convention).
For such a game with maximum possible subtraction of $16$, you were guaranteed ...
- 25.1k
2
votes
Accepted
Inertia groups of totally ramified extensions
As stated in the comments, you actually have $e=3$ and $f=1$. Here are two ways to see this. Let $\newcommand{\Q}{\mathbb{Q}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\F}{\mathbb{F}} \newcommand{\O}{\...
- 20.2k
17
votes
Conjecture: If $n$ is an odd positive integer then $\gcd\left(2^{n}+5,5^{n}-3^{n}\right)=1$.
A quick search has revealed that when
$$n = 3539969049025$$
the numbers $2^n + 5$ and $5^n - 3^n$ have common factor
$$p = 103408180634401.$$
The python code to check this is pasted below
...
- 11k
1
vote
What is the probability that $250$ random digits contain $7777$ , $8888$ and $9999$?
Because of the symmetry between $7$, $8$, and $9$, there's a much smaller matrix that can be used to arrive at the exact answer than that proposed by @Daniel Martin. Let $\mathsf{A}$ be the state ...
- 42.7k
2
votes
An Exploration of Cube Relations in 3-4-5 Pythagorean Triples?
Welcome to Math.SE! ... First of all, congratulations on perceiving a pattern; that's what mathematics is all about!
Skipping-over your initial relation (which I believe doesn't capture your intention)...
- 80.3k
1
vote
Accepted
Odd integer Dirichlet approximation
[Posted as an answer, at OP's request]
W. T. Scott, "Approximation to real irrationals by certain classes of rational fractions", Bull. Amer. Math. Soc. 46, 124-129, shows that if $\alpha$ ...
- 463k
2
votes
Accepted
$n\ =\ \lfloor \sqrt{2}a\ \rfloor +\lfloor \sqrt{3}b\rfloor$
I have mentioned the Beatty Sequence in the comment, but seeing the AOPS post the solution there is quite clear and brief, so I’m posting an explanation of it.
First, OP on AOPS(OP below) wrote:
$$\...
- 3,086
1
vote
Accepted
Size of prime divisors of $\gcd(a^3 + 2, b^3 + 2)$
This is not a proof, but I've added enough numerical explorations to my previous heuristics that I hope you'll forgive me putting it in the "answer" field.
Heuristics (cf. the comments above)...
- 7,834
0
votes
Probability that a natural number N is prime.
You are absolutely correct $-$ the question is meaningless unless your friend specifies a probability distribution on the natural numbers. This is because there is no uniform distribution on the whole ...
- 66.5k
2
votes
Krull dimension of the adele ring
Let's treat $K=\Bbb Q$ first. It's well-known that $\Bbb A_{\Bbb Q}\cong (\Bbb Q \otimes_{\Bbb Z}\widehat{\Bbb Z}) \times \Bbb R$. We can just focus on $\Bbb Q \otimes_{\Bbb Z}\widehat{\Bbb Z}$ for ...
- 23.6k
1
vote
The Hasse invariant at cuspidal elliptic curves in a generically ordinary family
Figuring this out was fun!
I feel like part of my answer should be intuitive, except I’m not sure how to make it rigorous at all. The gist is that $\mathbb{G}_m$ really, really, doesn’t want to be ...
- 36.7k
1
vote
On Thue-Siegel-Roth Theorem.
Is this proof only available for quadratics?
Yes.
In general, the following is true, and follows from an argument not so different from yours:
Lemma: If $\alpha$ is an irrational root of an ...
- 188
0
votes
What is the best book learn Galois Theory if I am planning to do number theory in future?
The recently published book Introduction to Galois Theory by David Hernandez and Yves Laszlo is an excellent resource for beginners.
"The authors introduce Galois theory from a contemporary point ...
Top 50 recent answers are included