Questions on more advanced topics of number theory, such as quadratic residues, primitive roots, prime numbers, non-linear Diophantine equations, etc. Consider first if (elementary-number-theory) might be a more appropriate tag before adding this tag.

learn more… | top users | synonyms (1)

-3
votes
1answer
35 views

Question on number theory [closed]

If a²+(5/2)b²+c²= 2ab+bc+ca then a+2b+2c equals what? I am unable to think how to solve it.. Please help
0
votes
1answer
47 views

Following the previous question: Existence of the natural density …

Following the previous question: Let $A=\{a_n\}$ is a strictly-increasing sequence of positive integer. The natural density of this sequence is defined by $\delta(A)=\lim_{n\rightarrow \infty} \frac{...
1
vote
1answer
41 views

Splitting of primes in real cyclotomic field

The question is from Marcus' book, "Number Fields" (exercise 12, Chapter 4) Let $\omega= e^{\frac{2\pi i}{m}}$ and $p$ be a rational prime not dividing $m$. Then how does $p$ split in $\mathbb{...
2
votes
2answers
55 views

Number of even numbers having digit 2 in them.

I am trying to count numbers from 1 to N which exist in A121022 but I am unable to think of solving in better than O(NLog(N)) , can you suggest a better algorithm?
1
vote
1answer
35 views

Some questions on Euler's phi function

I was reading Number Theory by George E. Andrews (Dover 1994,) problem set 6-1, p. 81. (I'm not a student; I just find problems like these entertaining like some people enjoy crosswords or Sudoku.) ...
0
votes
2answers
57 views

Can an irrational number be expressed as a sum of other irrational numbers, at least one of which is not an integral multiple of the required number?

For example, $\pi = Ae + B\sqrt 2+ \cdots$ ($A,B,\ldots\in\mathbb R$) (Equations like "$\pi = 3\pi - 2\pi$" are not allowed.)
4
votes
2answers
79 views

How can we create arbitrarily long instances of the Euclidean algorithm?

How can we create arbitrarily long instances of the Euclidean algorithm? What kind of numbers are useful? What is the relationship between the size of these numbers and the number of steps?
11
votes
6answers
2k views

Why does the Euclidean algorithm always terminate?

Why does the Euclidean algorithm always terminate? Can we make this effective by bounding the number of steps it takes in terms of the original integers?
9
votes
1answer
135 views

Is $n^7 - 77$ ever a Fibonacci number?

As the question title suggests, is $n^7 - 77$ ever a Fibonacci number, where $n$ is a integer?
0
votes
1answer
47 views

Given the value of a polynomial mod $611953$, find $x$?

Given a polynomial of degree $n$, and a value $\pmod{611953}$, find the possible $x$ at which this value occurs? For example a polynomial $p(x)$ is given of some degree $n$, and a number is given ...
2
votes
0answers
28 views

How to do this integral? $\int_{-i\infty}^{i\infty}F_{\psi}(z) dz$?

Let $\psi$ be a character with conductor $f_\psi$. Define $$F_\psi(z)=\begin{cases}\sum_{n=1}^{\infty}\psi(n)e^{2\pi i nz}&\text{ if }& \text{Im}(z)>0\\ -\sum_{n=1}^{\infty}\psi(-n)e^{-2 \...
1
vote
4answers
83 views

Does $18^{247}$ divide (500!)?

I wanted to find the highest power of 18 that divides 500! I did this : $18=6*3=(2*3)*3$ For 2, highest power is 494 For 3, highest power is 247, Therefore highest power of 6 is min{494, 247}...
3
votes
1answer
28 views

Factorization of primes in normal closure of Quartic Field

Motivation for the question comes from Marcus' book on Number Fields (exercise 13, Chapter 4). Let $K= \mathbb{Q}[\sqrt[4]{m}, i]$ where $i=\sqrt{-1}$, $m\in \mathbb{Z}$ and $m$ is not a square. ...
1
vote
1answer
72 views

How to factorize a number into prime numbers

I have to compute the Legendre symbol $4307 \choose 7549$, so I have to factorize $4307$ into prime numbers. Is there any mathematical shortcut to do it?
0
votes
0answers
24 views

Is it conjectured there infinitely primes $p$ such that M($p$) is a Mersenne Prime, where p is of an arithmetic progression?

Are there infinitely many primes $p$ of the form $an+d$ for fixed $a$ and $d$ coprime, and that $2^p-1$ is also prime? In other words, there are infinitely many primes $p$ $=$ $a$ $\pmod d$ ($a$ and ...
1
vote
2answers
101 views

How to read a proof? [closed]

As I go deeper and deeper into upper division math courses, I find some proofs to be very challenging to understand. Right now I am trying to understand Gauss's lemma in number theory and I can't ...
0
votes
1answer
27 views

Computing the Legendre symbol $6 \choose 11 $

Compute the Legendre symbol $6 \choose 11$ By euler's critetion, ${6 \choose 11}=-1$, but ${6 \choose 11}={3 \choose 11 }{2\choose 11}=-1*-1=1$. I am confused about that result.
0
votes
1answer
45 views

What is the equivalent statement of GRH in term of Redheffer Matrix or Farey Sequences?

We all know that Riemann Hypothesis (RH) has many equivalent statements. There is one statement which expresses RH in term of Redheffer matrix, there is another equivalent statement of RH which ...
0
votes
0answers
13 views

Effective estimates for k-almost primes

Given an integers $k$ and $\ell$ and a real numbers $\varepsilon>0$, define $f(k,\ell,\varepsilon)$ as the least $x_0$ such that for all $x>x_0$ the fraction of $\ell-$rough numbers up to $x$ ...
2
votes
4answers
70 views

Decreasing sequence numbers with first digit $9$

Find the sum of all positive integers whose digits (in base ten) form a strictly decreasing sequence with first digit $9$. The method I thought of for solving this was very computational and it ...
3
votes
2answers
102 views

In abstract algebra, what is an intuitive explanation for a field?

Wikipedia has the following to say about fields. In mathematics, a field is one of the fundamental algebraic structures used in abstract algebra. It is a nonzero commutative division ring, or ...
4
votes
1answer
46 views

Abuse of notation for infimum and supremum

I would like to take the infimum and supremum of two sets $(\frac{1}{2} e^{8m+4} - 1, e^{8m+4} - 1)$ and $(\frac{1}{2} e^{8m+4}, \frac{3}{2}e^{8m+4})$, but writing $\sup((\frac{1}{2} e^{8m+4}, \...
9
votes
0answers
51 views

What to keep in mind when attempting proof of basic properties of divisibility/what techniques are useful/what's the intuition for showing them?

So I am currently trying to prove some basic divsiibility relations, as follows. If $a \mid b$ and $a \mid c$, then $a \mid (b + c)$. If $a \mid b$ and $s \in \mathbb{Z}$, then $a \mid sb$. ...
2
votes
1answer
26 views

ceiling of an expression

If we need to find the ceiling of this expression (A-11)/100 then is it correct to simply write the above expression as ...
1
vote
3answers
71 views

Product of the first $n$ Fibonacci numbers is a perfect square

Suppose that $F_{n+2}=F_n+F_{n+1}$ and $F_1=F_2=1$. Can the number $P_n=F_1\cdots F_n$ be a perfect square if $n\ge 3$?
0
votes
2answers
31 views

Prove that If $m'$ is a common multiple of $s$ and $t$, then $m | m'$. Here $m$ is the LCM of $s$ and $t$.

Prove that If $m'$ is a common multiple of $s$ and $t$, then $m | m'$. Here $m$ is the LCM of $s$ and $t$. Although the statement is intuitively clear to me I don't know how to prove.
4
votes
1answer
57 views

n-th roots of unity summing to $0$

Let $\zeta = e^{2\pi i/n}$ be an $n$-th root of unity, and let $S = \{\zeta^m|m=0,1,\ldots,n-1\}$ be the corresponding sets of all $n$-th roots of unity. Let $k \leq z$. Let $C \subseteq S$ such ...
0
votes
0answers
57 views

The random matrix for Riemann Hypothesis, is it corresponding to an operator in quantum mechanics or in quantum field theory?

Odlyzko showed that the distribution of the zeros of the Riemann zeta function shares some statistical properties with the eigenvalues of random matrices drawn from the Gaussian unitary ensemble. This ...
0
votes
0answers
21 views

total numbers from 1 to N whose second smallest number is known

We are given a value N. We need to find how many numbers from 1 to N have a number i as the second smallest non divisor if their smallest non divisor is j? Let us say N=10 .The second smallest non ...
0
votes
0answers
51 views

Original numbers

Assuming Goldbach's conjecture, let's write $r_{0}(n):=\inf\{r\geq 0, (n-r,n+r)\in\mathbb{P}^{2}\}$. GC is equivalent to the inequality $r_{0}(n)<n$. In fact, much more should be true, since one ...
0
votes
1answer
44 views

If $(a,b)=1$ then there exist positive integers $x$ and $y$ s.t $ax-by=1$. [duplicate]

How can i prove that if $\gcd(a,b)=1$ there exist $x>0$ and $y>0$ such that $ax-by=1$?
0
votes
1answer
29 views

Question about reduced residue system

Let $1,2,.......,p-1$ be a reduced residue system mod $p$ where $p$ is a prime number. If $\gcd\left(k,p\right)=1$ for an integer $k$ then we can say $k,2k,\dots,k(p-1)$ is also a reduced residue ...
0
votes
0answers
38 views

Need help with the explanation of a theorem

http://people.ucsc.edu/~yorik/Math110/PDF/QuadRec.pdf My question is in theorem 3. I understand until it says $a={p-1}/2$ if $p \equiv 1(\mod 4)$ and $a=p-(p-1)/2$ if $p \equiv 3(\mod 4)$. Why is ...
-1
votes
2answers
36 views

Prove that Carmichael number has no primitive roots

Prove that if $n$ is a Carmichael number, then $n$ has no primitive roots. This seems tricky to prove, and the only logical explanation for this is that it contradicts the basis of the Lucas Primality ...
1
vote
0answers
67 views

How to determine redundant elliptic curves?

When we enumerate elliptic curves $y^2 = x^3 + ax + b$ over a finite field, how do we determine redundant ones, i.e. ones that are equivalent to others?
1
vote
1answer
15 views

Proving $(n/p)$, a Legendre symbol, is multiplicative

Proof if $p|n$ or $p|m$ then $p|nm$, so $(n*m)/p=0=(n/p)(m/p)$ if p doesnt divide n then , $$(n*m/p)=(n*m)^{{p-1}/2}(mod \text{ } p)$$ $$(n*m/p)=n^{{p-1}/2}m^{{p-1}/2}(mod \text{ } p)$$ $$(n*m/...
-1
votes
0answers
22 views

Existence of elliptic curves for thriples a,b,c

I am not a mathematics student but i have fascination with advance algebra so i read random articles about it without actually understanding it (lol). I'm not sure but I think I read an article a long ...
0
votes
1answer
22 views

Question about proof of euler's criterion

When a is quadratic residue of the odd prime p, we arrived to the conclusion $(p-1)! \equiv -a^{{p-1}/2}\pmod{p}$. How does that imply $a^{{p-1}/2} \equiv 1\pmod{p}$
1
vote
1answer
72 views

When can $\frac{3}{n}$ not be written as the sum of two reciprocals of natural numbers?

Show that the set of natural numbers $n$ for which $\frac{3}{n}$ cannot be written as the sum of two reciprocals of natural numbers ($S = \left\{n \mid \frac{3}{n} \neq \frac{1}{p}+\frac{1}{q}\right\}$...
5
votes
2answers
64 views

Proving Wilson's theorem

Wilson's theorem: if $p$ is prime then $(p-1)! \equiv -1(mod$ $ p)$ Approach: $$(p-1)!=1*2*3*....*p-1$$ My teacher said in class that the gcd of every integer less than p and p is 1, so every ...
0
votes
2answers
51 views

Prove this Inequality using Induction

Prove using induction that $|\prod_{j=1}^{n}a_{j} - 1| \leq \sum_{j=1}^{n}|a_{j}-1|$ for $|a_{j}| \leq 1$. So far, I have the Base Case: When $n=1$, we have $|a_{1} - 1| = |a_{1} - 1|$. The ...
2
votes
1answer
299 views

Reducing an indicator function summation into a simpler form.

Context I am attempting to reduce the space I need to store in an array in a program. I have made it so that the indices are always sorted. There are no indices where they are equal, and no indices ...
2
votes
4answers
70 views

$\frac{\phi(m)}{m}$ is dense in $[0,1]$

Let $n$ be a natural number, $n \geq 2$, and let $\phi$ be Euler's function; i.e. $\phi(n)$ is the number of positive integers not exceeding $n$ and coprime to $n$. Given any two real numbers $\alpha$ ...
0
votes
2answers
84 views

What is a Diophantine equation, and why should we care about them? [closed]

As the question title suggests, what is a Diophantine equation, and why should a high schooler learning about elementary number theory care about them?
5
votes
0answers
43 views

Explaining difference between natural numbers, integers, rationals, reals, complex numbers, Gaussian integers [closed]

As so far as usage in elementary number theory goes, what is the difference between the natural numbers, the integers, the rational numbers, the complex numbers, and the Gaussian integers?
2
votes
2answers
39 views

Mills Test Running Time

Can Miller's Test be replaced with the bound below in hopes that it would make a faster general-purpose primality test (compared to ECPP). If $n$ is an $a$-SPRP for all primes $a$ $<$ ($\log_2 n$)...
18
votes
3answers
348 views

A few questions on the Gaussian integers

I have a few questions surrounding the Gaussian integers, which I hope can be answered together in one fell swoop. The Gaussian integers are defined as $\mathbb{Z}[i] = \{x + iy : x, y \in \mathbb{Z}...
4
votes
1answer
43 views

Intuition for basic fact surrounding Gaussian integers.

What is the intuition behind the following fact? Among the odd primes: Those that have remainder $3$ upon division by $4$ remain prime in $\mathbb{Z}[i]$. Those that leave remainder $1$ ...
20
votes
0answers
186 views

$x_1 = 2$, $x_{n + 1} = {{x_n(x_n + 1)}\over2}$, what can we say bout $x_n \text{ mod }2$?

Let$$x_1 = 2, \quad x_{n + 1} = {{x_n(x_n + 1)}\over2}.$$What can we say about the behavior of $x_n \text{ mod }2$? Is there an exact formula for $x_n \text{ mod }2$?
0
votes
1answer
35 views

Smallest integer such that $\dfrac{C_k}{n+k+1}\binom{2n}{n+k}$ is an integer

It is well known that the binomial coefficients $\binom{n}{k} = \dfrac{n!}{k!(n-k)!}$, $0 \leq k \leq n$, are positive integers. The factorial $n!$ is defined inductively by $0!= 1$ and $n! = n \cdot (...