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)

1
vote
1answer
15 views

Proving $\gcd(N^a-1,N^b-1)=N^{\gcd(a,b)}-1$.

I have come by one solution only, but things were derived too quickly without me understanding how or why. How does knowing that $\gcd(a,b)$ is a factor and a and b, actually derive that ...
0
votes
1answer
18 views

Show that $a^{p+1\over 4}$ solves the equation $x^2 ≡ a \pmod p$.

Let $p \equiv3 \pmod 4$ be a prime number, and let $1 \le a\le p − 1$ be a quadratic residue. Show that $a^{p+1\over 4}$ solves the equation $x^2 ≡ a \pmod p$. I know that if $(a,n)=1$ and $p\ge ...
0
votes
0answers
12 views

Roadmap to $p$-adic numbers: where a self-learner should look for references

TL;DR at the end of the question. I’m currently trying to learn as much as possible about p-adic numbers. I’m not sure what is the most fascinating part of the theory, but the use of the adjective ...
1
vote
1answer
20 views

RSA fixed point

What is the number of RSA fixed points, in other words how many $m$ are there such that $$m^e\equiv m \pmod{n}$$ where $n=pq$, for primes $p,q$. I know that the answer is ...
0
votes
0answers
10 views

Does there exists a positive $t$ that satisfy this given condition?

I am curious about the validity of my claim concerning the equations: $(2k-1)t+1$ (1) $(2k^2-2k)t+(2k-1)$ (2) where $k=2,3,4,...$ My claim is for almost all $k$ or for infinitely many $k$, there ...
0
votes
0answers
22 views

a question in De koninck and luca's analytic number theory

what is your idea,can you introduce a book for these kind of problems?
3
votes
4answers
53 views

Product of two integers of the form $x^2+my^2$ is of the same form.

Let $x,y,a,b\in \mathbb Z$. Prove that there are integers $c$ and $d$ so that \begin{equation*} (x^2+y^2m)(a^2+b^2m)=c^2+d^2m. \end{equation*} I'm stuck, I took the product and got ...
0
votes
1answer
13 views

List products in descending order

I'm doing a problem from Project Euler where I need to examine a descending order of multiples of 3 digit numbers ...
0
votes
0answers
13 views

Is there a match between this modified prime pi function and the Log integral function?

Table T is defined as through the properties that accumulated row sums give prime numbers, while accumulated column sums give composite numbers. ...
0
votes
1answer
28 views

Elliptic curve $y^2= x^3 + x$ over the finite field $\mathbb{F}_p$ with $p \geq 3$.

Consider the elliptic curve $$E: y^2= x^3 + x$$ over the finite field $\mathbb{F}_p$ with $p \geq 3$. I want to show that $|E(\mathbb{F}_p)| \equiv 0 \mod 4$. I know that, if $p \equiv 3\mod 4$, ...
4
votes
4answers
59 views

Proving that $\varphi(n)=n\prod (1-1/p)$ without using multiplicativity

$$\varphi(n)=n\prod_{p \ \text{prime}} (1-1/p)$$ Can this useful formula be derived without using the fact that Euler's totient function is multiplicative?
1
vote
0answers
34 views

Is the Ulam Spiral just a coincidence?

I was messing around with the Ulam spiral because I was a little skeptical on it having any actual relevance. I noticed that if you lay out the spiral and then circle all the even numbers, it displays ...
1
vote
0answers
28 views

Simple $\{-1,0,1\}$ equation set

I'm trying to find the shortest path, getting from $x=0$ to $x=k$ in a certain problem, where I can slowly accelerate and decelerate. It comes down to finding the smallest $n$ and set of values ...
0
votes
0answers
5 views

Space complexity of the GNFS

The time complexity of the general number field sieve is generally quoted as $L_n\left[\frac{1}{3}, \sqrt[3]{\frac{64}{9}}\right]$. I'm looking for a credible reference (something that can be quoted ...
3
votes
0answers
28 views

Order of prime ideals over split primes in the class group.

Let $P$ be a prime ideal of $\mathcal O_K$ ($K$ a quadratic field) and let $P$ have norm $p$ where $p$ is a split prime. Is it possible for the ideal class $[P]$ to have order less than three? I feel ...
3
votes
1answer
59 views

The elliptic curve $y^2 = x^3 + 2015x - 2015$ over $\mathbb{Q}$

Consider the elliptic curve \begin{equation*} E: y^2 = x^3 + 2015x - 2015~\text{over}~\mathbb{Q}. \end{equation*} I want to prove that $|E(\mathbb{F}_7)| = 12$, that $|E(\mathbb{F}_{19})| = 19$ and ...
1
vote
1answer
16 views

Solve quadratic congruences.

$x^2= -1 (mod 43)$. I want know How to solve this problem and also what will be the general approach for solving any of such quadratic congruences.
2
votes
2answers
52 views

Finding the solutions of $x^2\equiv 9 \pmod {256}$.

Find the solutions of $x^2\equiv 9 \pmod {256}$. I try to follow an algorithm shown us in class, but I am having troubles doing so. First I have to check how many solutions there are. Since $9\equiv 1 ...
2
votes
2answers
85 views

Prove an inequality of Prime Numbers

The problem on which I am currently stuck is, Is it true that, $$x+y< \dfrac{p_{\pi(x)}+p_{\pi(y)}+p_{\pi(x)+1}+p_{\pi(y)+1}-2}{2}$$ for all sufficiently large $x$ and $y$, $x+y$ is a prime ...
1
vote
0answers
16 views

How to find a set of integer vectors (of length L) such that all its subsets with size L are linearly independent?

Given a number $M\geq L$, how to find a set of $M$ vectors in $\mathbb{Z}_{\geq0}^{L}$, say $S=\{\mathbf{a}_1,\cdots,\mathbf{a}_L\}$, such that: 1-All subsets of $S$ with size $L$ are linearly ...
0
votes
1answer
19 views

Is $(a^s\pmod{n})^k = a^{sk}\pmod{n}$?

Is $(a^s\pmod{n})^k = a^{sk}\pmod{n}$? And if it is, how come? I've thought about it and this is the only thing that makes sense (for now).
1
vote
0answers
13 views

Number of number in range $(l, r)$ satisfying XOR constarint

Here's a questions that's been bugging for some time now: Define the set $S_n = \{k \oplus (k + n)\mid k \in \Bbb Z, k ≥ 0\}$ (here, $\oplus$ is bitwise exclusive OR). To put it another way, $x$ ...
3
votes
1answer
30 views

$a,b,N$ are integers. Prove $x=x_0+\cdots$, $\ \ y=y_0+\cdots $ are solutions to $ax+by=N$

I'm asked to prove that if $a,b,N$ are integers, then in the equation: $$ax+by=N$$ I must prove that the integers $$x=x_0+\frac{b}{d}t,\ y=y_0-\frac{a}{d}t$$ are solutions to the equation. where ...
0
votes
1answer
23 views

Set theory, intersection of two sets

We have the set $D$ which consists of $x$, where $x$ is a prime number. We also have the set F, which consists of $x$, belongs to the natural numbers (positive numbers $1, 2, 3, 4, 5,\dots$) that is ...
0
votes
0answers
29 views

Least pair of numbers having at least $k$ distinct prime factors

Consecutive numbers with less than $k$ prime factors? shows that for every $k$, there is a pair $(n/n+1)$, such that $n$ and $n+1$ both have at least $k$ distinct prime factors. The object is to ...
0
votes
2answers
35 views

Hexadecimal representation of tenths place of $\frac{A}{C}$

So we can write $$\frac{A}{C}= a_1 \times 10^{-1} + a_2 \times 10^{-2} + a_3 \times 10^{-3} +\cdots$$ How do I find the hexadecimal representation of $a_1$ where all numbers and variables are in the ...
0
votes
2answers
46 views

can this decimal number be converted into a fraction?

Can $$ 0.45647456647456664745666647456666647456666664745666666647456666666647\dots $$ be converted into a fraction of $\frac{N}{M}$ where $N$ and $M$ are integers? I know there is an algorithm ...
0
votes
2answers
39 views

Find the number of possible values of $a$

Positive integers $a, b, c$, and $d$ satisfy $a > b > c > d, a + b + c + d = 2010$, and $a^2 − b^2 + c^2 − d^2 = 2010$. Find the number of possible values of $a.$ Obviously, factoring, ...
1
vote
0answers
39 views

Primes with the first $k$ digits of the solution of the equation $e^{-x^2}=x$

Let $s$ be the solution of the equation $e^{-x^2}=x$ The first $1000$ digits are : ...
2
votes
1answer
18 views

Sequences formed by integer evaluations of polynomials modulo $ p^{k} $, where $ p $ is a prime number and $ k \in \Bbb{N} $.

I have the following question. Let $ p $ be a prime number and $ k $ a positive integer. Let $ (a_{n})_{n \in \Bbb{Z}} $ be a two-way sequence in $ \Bbb{Z} / p^{k} \Bbb{Z} $. Then is it true that ...
2
votes
1answer
43 views

If $1+x+x^2+\cdots+x^{y-1}$ is a prime number then how prove that y is also a prime number?

If $1+x+x^2+\cdots+x^{y-1}$ is a prime number then how prove that $y$ is also a prime number? $x$ and $y$ are natural numbers
2
votes
0answers
13 views

Why is $m \infty$ the conductor of $K = \mathbb{Q}(\zeta_m)/\mathbb{Q}$?

Wouldn't this be saying that for all $p$ dividing $m$, $1 + p^{\operatorname{ord}_p(m)} \mathbb{Z}_p$ is contained in the group of local norms $N_{\mathfrak p/p}(K_{\mathfrak p})$, where $\mathfrak p$ ...
2
votes
0answers
19 views

Show that $U_i \rightarrow U_{i+e}, x \mapsto x^p$ is an isomorphism

Show that $U_i \rightarrow U_{i+e}, x \mapsto x^p$ is an isomorphism? Let $K$ be a finite extension of $\mathbb{Q}_p$ with uniformizer $\pi$, prime $\mathfrak p$, and ramification index $e = ...
4
votes
4answers
125 views

Show the following including triple statement

How do I show \begin{equation*} \sum \limits_{n=0}^{\infty} z^n=\prod \limits_{m=0}^{\infty}(1+ z^{2^m}) = (1-z)^{-1}? \end{equation*} The very left side is obvious because it is the geometric ...
0
votes
1answer
36 views

$f'(x) \equiv 0 \pmod{p}$ with $\deg f < p$ implies $f(x) \equiv c \pmod{p}$

Let $f(x) = P(x)/Q(x)$ where $P, Q \in \mathbb{Z}[x]$. Define $\deg f = \max(\deg P, \deg Q)$. Then as usual, $f'(x) = (Q(x)P'(x) - P(x)Q'(x))/Q(x)^2$. Suppose for some prime $p$, we had $f'(n) ...
1
vote
1answer
33 views

A Problem on the Prime Counting Function $\pi(x)$

Let $\pi(x)$ denotes the number of primes less than or equal to $x$. Also suppose that for some fixed $N$ we have $\pi(x+y)\ge\pi(x)+\pi(y)$. The problem is, Show that the equality in the above ...
24
votes
11answers
1k views

Computing irrational numbers

I am genuinely curious, how do people compute decimal digits of irrational numbers in general, and $\pi$ or nth roots of integers in particular? How do they reach arbitrary accuracy?
0
votes
0answers
19 views

Primality radius and quadratic reciprocity law

Given an integer $n>1$, I say that $r$ is a primality radius of $n$ if both $n-r$ and $n+r$ are primes. Goldbach's conjecture asserts that every integer greater than $1$ admits a primality radius. ...
0
votes
1answer
25 views

Show the following including number of divisors d(n)

I know how to show that $(d ∗ \mu)(n) = 1$ for all n ≥ 1.But.. I have two solutions. Firstly... result is trivial, because $d = 1 ∗ 1$ Secondly We know that both sides are multiplicative. Thus it ...
3
votes
2answers
61 views

My proof that an n digit number, times an n digit number can be expressed as a 2n digit number

I am very proud to say this is the first time I've actually used maths to endeavour to prove something without it being related to a question from my course! Statement In a base $B$, an $n$ digit ...
5
votes
1answer
39 views

Remainders of quadratic trinomial

The problem is to determine, whether there exist a quadratic trinomial $f(x) = ax^2 + bx +c$ with integer coefficients (with $a$ not a multiple of 2014), such that the numbers $\ f(1), \ f(2),\, ...
0
votes
3answers
35 views

Given a fixed positive integer $k$, find the number of pairs of integers $(x,y) \in \mathbb{Z}^2$ such that $x^2+y^2=5^k$

Given a fixed positive integer $k$, find the number of pairs of integers $(x,y) \in \mathbb{Z}^2$ such that $$x^2+y^2=5^k$$ Attempt: Clearly $x$ and $y$ cannot have the same parity. Assume that ...
5
votes
2answers
69 views

Find all solutions in N of the following Diophantine equation

$(x^2 − y^2)z − y^3 = 0$ i divide by $z^3$ and look for rational solutions of the equation $A^2 − B^2 − B^3 = 0.$ The point $(A,B) = (0, 0)$ is a singular point, that is any line through this point ...
0
votes
0answers
44 views

Number theory / decimal representation

Prove that for any $n\in\mathbb{N}$ there exists a number $m\in\mathbb{N}$ such that the decimal representation of $m^2$ has $n$ ones at the beginning and some combination of $n$ ones and twos at ...
-1
votes
3answers
65 views

Confused about transcendental numbers [on hold]

I'm little confused about the type of numbers that had been known, for example, consider a polynomial equation with rational and irrational coefficients of a degree p-prime number that is greater than ...
3
votes
2answers
70 views

Prove or disprove that $a^{\phi(n) + k} \equiv a^{k} \mod{n}$

Prove or disprove that $$ a^{\phi(n) + k} \equiv a^{k} \mod{n} $$ where $\phi(n)$ is Euler's totient function, for all positive integers $a$ and $n$, as long as $k$ is $\geq$ the ...
-2
votes
1answer
51 views

How many Gaussian Integers $z$ divide 10 [on hold]

How many Gaussian Integers $z$ divide 10, in that $10=z\times{w}$ for some Gaussian Integer $w$?
1
vote
1answer
50 views

Solvability of the congruence $(x+a)^n\equiv x^n\pmod p$ in $x$

When thinking about solving the diophantine $x^n-y^n=1001$ I noticed that my knowledge about the prime factorisation of $x^n-y^n$ does not suffice to attack such diophantines in general. Note I'm ...
4
votes
0answers
36 views

Number of squarefree numbers and the Basel problem

Who discovered/proved that there are about $$ \frac{x}{\zeta(2)} $$ squarefree numbers up to $x$, or (roughly) when was this first known? Today I think this is considered 'obvious', but I don't know ...
4
votes
2answers
40 views

A Mertens-like product over primes

MathWorld's page Prime Products gives the 'related result' (7) to Mertens' theorem: $$ \lim_{n\to\infty}\log p_n\prod_{k=1}^n\frac{1}{1+1/p_k}=\frac{\pi^2}{6e^\gamma}. $$ Does this identity have a ...