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)

0
votes
0answers
17 views

An elementary residue problem

Given $A,B\in\Bbb N$ with $|A-B|=o(\min(A,B))$ how to find $C,\psi\in\Bbb N$ such that $|\psi-A^6|=o(A^6)$, $|\psi-B^6|=o(B^6)$, $|C-A^5|=o(A^5)$, $|C-B^5|=o(B^5)$ holds with ...
1
vote
1answer
22 views

Squaring both sites when units are different?

Given $((9) \text{inches})^{1/2} = ((0.25) \text{yards})^{1/2}$, then which of the following statements is true? $((3) \text{inches}) = ((0.5) \text{yards})$ $((9) \text{inches}) = ((1.5) ...
-2
votes
0answers
17 views

Does the Riemann Hypothesis consider mirror symmetry on its non-trivial zeros?

Setting the bottom corners of the square 1 on the center of two intersected circumferences and taking as center of symmetry the center of that intersection, it's possible to project the square 1 ...
1
vote
1answer
17 views

theory number, number of solutions, not prime numbers

I have been troubled by this: $\tau(2^x \times 3^y)=m$ Being $x$, $y$ and $m$ positive integers Then the number of solutions is $\tau(m)$ I already have done the proof for m prime however cant do ...
3
votes
1answer
85 views

Is it possible to find a perfect cube like 111…11?

Can we find a perfect cube like $111...111$(all digits are $1$), apart from the number $1$ itself? It's easy to prove that there can't be anything like $111...11$ that is a perfect square besides ...
1
vote
1answer
13 views

Prove that there exists infinitely many primes of Digital root $2,5$ or $8$

I am highly interested in properties of digital root. Digital Root: Digital root of a number is a digit obtained by adding digits of number till a single digit is obtained. It's clear that Digital ...
2
votes
0answers
28 views

Logic problem: “John's safe's passcode'” question from earlier, with more detail [on hold]

The answer and explanations have already been given at its original post (on Facebook) but I'd like to confirm that it is indeed solvable since there are still some parts I don't quite understand. ...
1
vote
0answers
23 views

Examples of equations that creates pseudorandom numbers

I just want to know more examples of equations that creates pseudorandom numbers. Right now I only know the Elliptic Curves. $y^2 = x^3 - 3x + b \pmod p$
0
votes
0answers
65 views

Is there a solution for this problem ?? [on hold]

There a man name john , john has a big safe but he forgot the password. he remembered : the password contain 10 distinct numbers If you add a certain digit in front, the aforementioned amount will ...
1
vote
0answers
33 views

Step to prove twin primes' conjecture: $\liminf_{n\to\infty}(p_{n+1}-p_n)<7\cdot10^7$

Today I have found that the Chinese mathematician Yitang Zhang has proven in 2013 that the sequence $d_n=p_{n+1}-p_n$ where $p_n$ is the $n$th prime has a finite inferior limit (and in fact, lesser ...
1
vote
0answers
14 views

Does there exist a $k$ such that for all $n \ge 3$, $\text{gpf}(\lfloor n^{(\log{n})^k} \rfloor) \gt n$?

Does there exist a $k \in \mathbb{R}$ such that for all $n \in \mathbb{N}, n \ge 3$, $\text{gpf}(\lfloor n^{(\log{n})^k} \rfloor) \gt n$, where $\text{gpf}(x)$ is the greatest prime factor of $x$? I ...
0
votes
2answers
36 views

Special case of Pillai's conjecture

Pillai's conjecture is a generalization of Catalan's conjecture. It's say that for fixed positive integers $A, B, C$ the equation $Ax^n - By^m = C$ has only finitely many solutions $(x,y,m,n)$ with ...
2
votes
3answers
32 views

Product of two primitive roots $\bmod p$ cannot be a primitive root.

I recently proved that the product of all primitive roots of an odd prime $p$ is $\pm 1$ as an exercise. As a result, I became interested in how few distinct primitive roots need to be multiplied to ...
2
votes
1answer
21 views

Find all elements of multiplicative order 18.

Find all elements of $\mathbb{Z}_{19}^*$ of multiplicative order $18$. I started by using Euler's Theorem and since gcd(18, 19) = 1 it implies that $a^{\phi (19)} \equiv 1 \pmod n$. Which means ...
0
votes
2answers
28 views

$17x+11y \equiv 7 \pmod {29}$ and $13x+10y \equiv 8 \pmod {29}$. What are x and y?

Congruency question: if $17x+11y \equiv 7 \pmod {29}$ and $13x+10y \equiv 8 \pmod {29}$, we need to find $x$ and $y$. There may be more than one answer. Not sure how to go about this; any help ...
0
votes
0answers
20 views

eigenbasis of old forms

Let $S_k(N)$ be the space of weight $k$ cusp forms with respect to $\Gamma_0(N)$ for $1\leq N\leq 100$. We have a decomposition: $$S_k(N)= S_k^{\text{new}}\oplus S_k^{\text{old}}$$ Suppose that we ...
-1
votes
0answers
14 views

On the upper bound for the Chebyshev function: What am i missing here?

The Chebyshev second function is defined as $\psi(x) = \sum_{p^m \leq x} \log p$, where $p$ is a prime, $m\geq 1$ is an integer and $n=p^m$. It is known that there exist positive constants $c_1$ and ...
0
votes
3answers
39 views

Variation on Fermat Little Theorem

Does the following variation of Fermat Little Theorem hold? How do you prove it? Let $p$ be a prime number greater than $3$. Then there exist a natural non-prime $m > 1$ such that ...
1
vote
0answers
18 views

Denominators of harmonic numbers: asymptotic behaviour.

About the sequence $d_n$ of the denominators of harmonic numbers, I know these facts: It is unbounded, since $p\mid d_p$ for any prime $p$. It contains only one $1$. What more is known? Specially, ...
9
votes
1answer
74 views

Is there a polynomial such that $F(p)$ is always divisible by a prime greater than $p$?

Is there an integer-valued polynomial $F$ such that for all prime $p$, $F(p)$ is divisible by a prime greater than $p$? For example, $n^2+1$ doesn't work, since $7^2+1 = 2 \cdot 5^2$. I can see that ...
2
votes
1answer
25 views

Complexity of generating a prime larger than $N$

Is it provably difficult to generate a prime larger than a prescribed $N$? For instance, if I want a prime of $1000$ digits, is there a way to do that deterministically, i.e., without resorting to AKS ...
3
votes
1answer
55 views

Show that the elements of the form $1+\zeta + \zeta^2 + \dots + \zeta^m$, with $1 \leq m \leq p-2$, are invertible in $\mathbb{Z}[\zeta]$

Let $\zeta = e^\frac{2 \pi i}{p}$, with $p$ prime. Show that the elements of the form $1+\zeta +\zeta^2 + \dots + \zeta^m$, with $1 \leq m \leq p-2$, are invertible in $\mathbb{Z}[\zeta]$. I know ...
2
votes
3answers
112 views

How do We know We can Always Prove a Conjecture?

The question asked here is, suppose we are given a a conjecture to prove in number theory (with numerical evidence showing its true). Say an important well studied conjecture that most will believe is ...
0
votes
3answers
44 views

Find the value of y in $11y \equiv 14 \pmod{19}$

Find the value of $y$ in $11y \equiv 14 \pmod{19}$. My issue is not with finding a solution. Using the Euclidean algorithm and Bezout's identity I get a final expression of: $$(11)(7)(14) - ...
1
vote
1answer
25 views

Prove that if $17 \not\mid n$, then either $17 \mid n^8+1$ or $17 \mid n^8-1$

Question is : Let $n$ be a natural number not divisible by $17$. Prove that either $n^8+1$ or $n^8-1$ is divisible by $17$. I tried to solve using Fermat theorem for a prime number $p$, and any ...
0
votes
1answer
16 views

Base 7 Conversion with Exponents

Explain how $56.42(4+3)^2=5642$ can be a true statement. I understand that we essentially need $(4+3)^2$ to act as $100$ in order for $56.42$ to become $5642$. However, if we operate in base $7$ and ...
3
votes
0answers
26 views

Does there exist $a\in\mathbb N$, $b\in\mathbb Z$ that $2^na+b$ is a square for all $1\le n\le5$?

We consider such $a\in\mathbb N$, $b\in\mathbb Z$, o numbers of the form $2^na+b$ is square to the largest possible number of values of $n=1,2,3,4,\ldots$. It is easy to see that for $a = 60 $, $ b ...
0
votes
0answers
12 views

Reducing a rectangular matrix of large rationals to small rationals

I have a large matrix (~1000 by ~2000), whose entries are purely rational numbers, typically involving large fractions, that is numbers (much) larger than 10^8 in denominator/numerator. The original ...
0
votes
0answers
29 views

Find k-th element of the sequence

Please, help me with effective algorithm to: Find k-th element of the sequence {n | (6n-1), (6n+1), (12n+5) are primes} Find k-th element of the sequence {n | (6n-1), (6n+5), (12n-7) are primes}
0
votes
2answers
30 views

How do I evaluate this sum :$\sum_{n=1}^{\infty}\frac{{(-1)}^{n²}}{{(i\pi)}^{n}}$?

I'm interesting to know how do i evaluate this sum :$$\sum_{n=1}^{\infty}\frac{{(-1)}^{n²}}{{(i\pi)}^{n}}$$, I have tried to evaluate it using two partial sum for odd integer $n$ and even integer $n$ ...
0
votes
0answers
15 views

what can we say about $\varphi^{-1}(2^a), \varphi^{-1}(2^\alpha), \varphi^{-1}(2^\beta)$ where $a=\alpha+\beta$?

Let us consider the Euler's totient function $$\varphi(n):=\#\{1\leq r\leq n: \gcd(r,n)=1\}$$ We also know that $$\varphi(mn)=\varphi(m)\varphi(n)\frac{d}{\varphi(d)}$$ where $d=\gcd(m,n)$. Now ...
4
votes
2answers
50 views

Is $\phi :SL_2(Z) \to SL_2(Z/NZ)$ still surjective if we replace Z with some ring of integers?

It is well known that the natural map $\phi :SL_2(Z) \to SL_2(Z/NZ)$ is surjective. So that the kernel, i.e. the principal congruence subgroup is of finite index. But what if we replace Z with some ...
0
votes
1answer
23 views

Number Theory Primes and Rationals

Question: Show that if the square of a rational number is an integer, than the rational number itself is an integer. Suppose the rational number is of the form $(\frac{m}{n})$, I have deduced that if ...
1
vote
2answers
42 views

If $(d,a)=1$ and $d|ab$ then $d|b$ .

Okay, checking to see if i'm on the right track. I essentially did the same prove for Euclid's lemma but exchanged the $d$ for the $p$. Is that the right idea? Or am I missing something?
0
votes
2answers
15 views

asymptotic and monotonically increasing properties of prime factorization function?

Questions We define $A(x)= \text{number of prime factors of x}$ For example $A(2 \times 3^2) = 3$ I noticed when $s_k = \frac{N!}{\prod_j n_j}$ and $\sum_{j} n_j = N$ $$ s_1 < s_2 \implies ...
1
vote
1answer
21 views

How many incongruent primitive roots does 13 have?

How many incongruent primitive roots does 13 have?: So far I know that phi(phi(13)) = phi(12) = 4, so there would be 4 primitive roots. And a RRS mod 13 is {1,2,3,...,12}. But I'm not sure where to ...
0
votes
1answer
12 views

Ultrafilter and upper natural densities

It is straightforward to show that there is an ultrafilter $\mathcal{U}_0$ on the positive integers such that every element $A\in \mathcal{U}_0$ satisfies $$d^\ast(A):=\limsup_{n\to +\infty} ...
2
votes
0answers
31 views

Are binary bit-strings the most efficient representation of integers?

There is no format more popular in the world than the representation of Integers: 32-bit and 64-bit strings are used by basically every single computer in existence and there's no practical reason to ...
6
votes
1answer
103 views

Is $k+p$ prime infinitely many times?

I have the following conjecture: Let $k\in\mathbb{N}$ be even. Now $k+p$ is prime for infinitely many primes $p$. I couldn't find anything on this topic, but I'm sure this has been thought of ...
2
votes
3answers
37 views

show $b_1b_2b_3\cdots b_{\phi(m)} \equiv 1 \pmod m$

show $b_1b_2b_3\cdots b_{\phi(m)} \equiv 1 \pmod{m}$ or $b_1b_2b_3\cdots b_{\phi(m)} \equiv -1 \pmod m$ where $b_1 < b_2 < b_3<\cdots< b_{\phi(m)}$ are the integers between $1$ and $m$ ...
0
votes
1answer
23 views

Gauss Limit using Prime Number Theorem

I need to show $\lim_{n\to\infty}\frac{Li(n)}{\pi(n)} =1$, where $Li(n)$ = $\int_{2}^{n} \frac{dx}{ln(x)}$. I know I need to use the Prime Number Theorem, and L'Hopital's rule. However, I am I can't ...
4
votes
2answers
49 views

Number theory: Can we reach from $(x_0,y_0)$ to $(x_1,y_1)$ ,with following transitions?

Given $2$ points in 2-dimensional space $(x_s,y_s)$ and $(x_d,y_d)$, our task is to find whether $(x_d,y_d)$ can be reached from $(x_s,y_s)$ by making a sequence of zero or more operations. From a ...
1
vote
1answer
20 views

$A(n) = f(m)$ numbers of $f(m)$ followed by $f(m)$ numbers of $0$. $f(m)$ is the remainder when $m$ is divided by $9$.

A series is formed in the following manner: $A(1) = 1; $ $A(n) = f(m)$ numbers of $f(m)$ followed by $f(m)$ numbers of $0$; $m$ is the number of digits in $A(n-1).$ Find $A(30)$. Here ...
0
votes
2answers
33 views

Let $n$ be positive and $a > 1$. Show that $\gcd(\frac{a^n - 1}{a-1}, a-1) = \gcd(a-1, n)$ [duplicate]

I know that $\frac{a^n - 1}{a-1}$ is a geometric series, but I don't know how that can help me solve it. This is not a duplicate question...
2
votes
1answer
91 views

Asymptotics of “ugly” function elucidate Goldbach's conjecture?

Question We now define the following "ugly" function: $$ A_c(s,r,n,m) = \begin{cases} 1 & \text{ if only $sr+nm=2c$ } \\ 0 & \text{otherwise} \end{cases} $$ How does the ...
1
vote
1answer
38 views

Greatest common divisor of $(2^{21}-1,2^{27}-1)$ [duplicate]

Find $\text{gcd}(2^{21}-1,2^{27}-1).$ My proof: We know that $2^{21}-1=(2^3)^7-1=8^7-1=(8-1)(8^6+\dots+8+1)=7(8^6+\dots+8+1)=7N_1$ and ...
1
vote
1answer
23 views

find all incongruent solutions to $x^2 \equiv 3$ (mod$7$) [on hold]

find all incongruent solutions to $x^2 \equiv 3$ (mod$7$) The only theorems I have learned to use in this scenario are the linear equation thm: $ax + by = gcd(a,b)$ and linear congruence thm. With ...
4
votes
1answer
41 views

Aren't Legendre's conjecture and Andrica's conjecture same?

If Legendre's conjecture is true, couldn't we easily obtain $\sqrt{p_{n+1}}-\sqrt{p_{n}}<1$ where $p_{n}$ is the $n$th prime? $$p_{n+1}<(\lfloor \sqrt{p_{n}} \rfloor + 1)^{2}<( \sqrt{p_{n}}+ ...
3
votes
6answers
117 views

If $p$ is prime then $2p+1$ cannot be square

How can I prove that $2p+1$ cannot be a square number if $p$ is prime? Is a contradiction proof enough where I assume true then show it as false eventually?
0
votes
2answers
141 views

About a sequence on Prime numbers.

I'm learning math so this may seem obvious but its not to me. In our other post titled "Is this iteration involving primes known?" Is this iteration involving primes known? An iteration is defined ...