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)

-6
votes
0answers
67 views

Lepore primality test and factorization . What is the complexity?

I have found an algorithm which tests if a number NR is primes . What is the complexity? I show only NR = X * Y, where NR = 6G + 1, X = 6a + 1, Y = 6b + 1, G, a and b natural numbers. X and Y are ...
2
votes
2answers
47 views

Proof that: $a=bq+r ,-\frac {|b|}{2}<r≤\frac {|b|}{2}$ [closed]

Proof that: Let $a,b$ any integers, with $b≠0$, Then there exist unique integers $q$ and $r$ surch that $$a=bq+r ,$$ where $$-\frac {|b|}{2}<r≤\frac {|b|}{2}$$ Note corolario: Let ...
2
votes
0answers
30 views

Besides the $3x + 1$ problem, for which similar problems are still unresolved regarding trayectory?

Generalize the $3x + 1$ problem as $cx \pm 1$, where $c$ is a positive odd integer and $x$ is a positive integer iterated through the function as far as possible to discover a cycle. If $x$ is even, ...
0
votes
2answers
64 views

Proof that every positive integer has at most one prime factor greater than it's square root?

I read the statement in the title somewhere but I can't find any proof. For a positive integer $n$, why can't there be 4 numbers $a, b, c, d$ ($b$ and $d$ are prime) for which $a < \sqrt{n} < ...
2
votes
0answers
39 views

Legendre symbol identity

I try to solve the following problems ($p$ is an odd prime) Find the sum $$\sum_{a=1}^{p-1}a \cdot \left (\frac{a}{p} \right)$$ Find the sum $$\sum_{a=1}^{p-1} 2^a \cdot \left (\frac{a}{p} \right)$$ ...
7
votes
5answers
177 views

If $ a + b + c \mid a^2 + b^2 + c^2$ then $ a + b + c \mid a^n + b^n + c^n$ for infinitely many $n$

Let $ a,b,c$ positive integer such that $ a + b + c \mid a^2 + b^2 + c^2$. Show that $ a + b + c \mid a^n + b^n + c^n$ for infinitely many positive integer $ n$. (problem composed by Laurentiu ...
3
votes
1answer
54 views

Power and Divisibility

Find all positive integers $n$ such that $7^n-1$ is divisible by $6^n-1$. Trying small cases, it seems that there's no such positive integer.
5
votes
2answers
74 views

Proving the irrationality of the concatenation of the $n$th powers of primes

Note: The apostrophes are meant to separate different groups of digits. Like, $0.{1^2}'{2^2}'{3^2}'{4^2}'\cdots=0.14916\cdots$. I wasn't able to come up with something better. It is easy to show ...
0
votes
0answers
25 views

Is this approach to Lehmer's totient problem going anywhere?

So Lehmer's totient problem states that $k\phi(n) = n-1$ and $k$ is integer and $n$ is composite. $p_{1}p_{2}...p_{a} = n$ and $n$ must be carmichael, therefore $p_{1}p_{2}...p_{a} \equiv 1 ...
6
votes
2answers
135 views

Variation of the Josephus problem

Suppose we have a circle of $2n$ people, where the first $n$ people are good guys and the people $n+1$ to $2n$ are bad guys. Can we always choose an integer $q$, such that if we execute successively ...
3
votes
2answers
86 views

Integer solutions to $x^2 + dy^2 = c$

I'm trying to find all integer solutions of an equation $x^2 + dy^2 = c$ with $d,c \in \mathbb{Z}_{>0}$. I'm well aware of the methods that exists when $d \in \mathbb{Z}_{<0}$ or when $c$ is a ...
1
vote
1answer
27 views

Sum of digits of polynomial smaller than of factorial

I'm trying to prove this : Let $f \in Z[X]$ then for sufficiently large $n$ we have $$s(f(n))<s(n!)$$ where $s$ is the sum of digits function. What I have so far : I thought this must be true ...
0
votes
0answers
47 views

Elliptic curve is self dual.

How to prove $E[p^\infty] \cong Hom ( T_E, \mathbb{Q}_p/\mathbb{Z}_p(1)) $ where $T_E$ denotes the Tate module of $E$ ?
0
votes
1answer
30 views

Integer solutions of a quadratic equation with combined variables

I'm having problems with finding all possible integers solutions of particular equations, like this one for example: $x^2 -xy + 2y^2 = 29$. What sets me off, is the term $xy$, I don't know how to deal ...
0
votes
1answer
18 views

Lattice points in simplices - reference request

I found this paper http://homepages.math.uic.edu/~yau/35%20publications/An%20upper.pdf which, in formulas (1.2) and (1.3), relates the number of non-negative and positive integer values that are ...
-1
votes
2answers
31 views

Prove that $\gcd(\frac{m}{a},\frac{m}{b}) = 1$ if $m$ is the $\mathrm{lcm}$.

My ideas were rewrite the terms in parenthesis in a such way that any other common divisor of $m/a$ or $m/b$ divides $1$.
7
votes
3answers
64 views

Is there any element of order $51$ in the group $U(103)$

Does there exist an element of order $51$ in the multiplicative group $U(103)$ ? Now if the element exist say $x$ then it satisfies the equation $$x^{51}\equiv 1\pmod {103}$$ . ...
2
votes
0answers
62 views

Arithmetic progression of squarefree integers?

Let $x$ be a given positive integer. I'm intrested in the longest arithmetic progression of squarefree integers within the interval $(x,x^2)$. Both constructive and nonconstructive results. For ...
0
votes
3answers
114 views

Proof that there are infinitely many prime numbers

I answered a question to prove that there are infinitely many prime numbers, but I'm not sure if my attempt is right. Can somebody help me to check if my attempt is right? I would like, if I am wrong, ...
1
vote
1answer
35 views

Why is this continued fraction expansion what it is?

We have to find the continued fraction expansion of the roots of $1553 t^2 + 6014 t + 5820 = 0$, that is, $(\sqrt{14356} - 6014) / 3106$ Simplifying, $(\sqrt{3589}- 3007) / 1553$ The continued ...
1
vote
1answer
30 views

Determine the smallest number such that the division by $12,20,38$ left the same remainder $10$.

I was studying gcd and I found this problem. No idea how to solve: Determine the smallest number such that the division by $12,20,38$ leaves the same remainder $10$.
7
votes
2answers
201 views

What is the smallest prime $p$ such that the next prime is greater than $p+2000\ $?

I studied this site https://en.wikipedia.org/wiki/Prime_gap and wondered if the smallest prime gap greater than $2000$ can still be determined, in other words : Which is the smallest prime $p$, ...
0
votes
0answers
15 views

Scope of expressions which determine whether a number is the sum of two triangles

It is straightforward to prove that for any prime $P$ of the form $4n+1$, $\frac{P-1}{4} + kP$ is the sum of two triangles if, and only if $k$ itself is. And for primes of the form $4n+3$ the same ...
2
votes
1answer
32 views

How to eliminate the leading coefficient in this congruence?

$$ax^2 = b \bmod m$$ I am trying to get rid of the $a$ so I can apply Tonelli-Shanks to the result to solve for $x$. But since $a$ and $m$ are not always coprime, I cannot always multiply both sides ...
0
votes
1answer
30 views

measure of $|\alpha-\frac pq|\lt\frac1{4q^2}$ with infinitely solutions

$\alpha\in[0,1]$, and $$|\alpha-\frac pq|\lt\frac1{4q^2}$$ has infinitely solutions $p, q\in\Bbb Z$, $\gcd(p,q)=1$. Let $E$ be the set of all such $\alpha\in[0,1]$, that is ...
0
votes
1answer
43 views

How to determine whether a large number is prime

In the introduction part of "Rational Points on Elliptic Curves", it was mentioned that there are very quick ways to check that an integer is itself a prime although it is virtually impossible to ...
3
votes
2answers
57 views

Does there exist integer such that there exist sum of powers congruent mod $p$?

Let $n \in \mathbb{N}$, $p$ prime. For arbitrary $C \in \mathbb{Z}$, does there exist $a_1, a_2, \dots, a_n \in \mathbb{Z}$ such that$$C \equiv \sum_{i=1}^n a_i^n \text{ }(\text{mod }p)?$$
-3
votes
1answer
81 views

Questions from an olympiad on number theory [closed]

The sum of the infinite series: $$ \frac{1}{2} + \frac{2}{8} + \frac{3}{16} + \frac{5}{32} + \frac{8}{64} + \frac{13}{128} + \frac{21}{256} + \frac{34}{512} +....$$ I am able to find the general term ...
6
votes
1answer
132 views

Does $(1^a+2^a+3^a+4^a+5^a)^b=1^c+2^c+3^c+4^c+5^c$ imply $(a,b,c)=(1,2,3)$?

Question : Is the following proposition true? Proposition : For positive integers $a,b,c$ where $b\ge 2$, if $$(1^a+2^a+3^a+4^a+5^a)^b=1^c+2^c+3^c+4^c+5^c$$then $(a,b,c)=(1,2,3)$. This is ...
1
vote
1answer
32 views

How do I get rid of the coefficient in this congruence?

$$ax^2 = b \bmod m$$ I am trying to get rid of the $a$ so I can apply Tonelli-Shanks to the result to solve for $x$. But since $a$ and $m$ are not always coprime, I cannot always multiply both sides ...
6
votes
1answer
116 views

Ramification in $\mathbb Q(i,\sqrt[4]\pi)/\mathbb Q(i)$

Let $\pi\ne1+i$ be a prime element of $\mathbb Z[i]$. I am interested in the ramification in the extension $\mathbb Q(i,\sqrt[4]\pi)/\mathbb Q(i)$, especially over $(1+i)$. I've tried for instance to ...
0
votes
0answers
31 views

Decomposition and valuation rings

I am reading Algebraic Number Theory by A. Fröhlich, M. J. Taylor, it first introduced the theory: $(K,u)$ be a field and its absolute value, $(K_u,\bar u)$ be its completion and absolute value ...
4
votes
3answers
120 views

Iterated square roots over finite field. When do we hit a nonresidue?

Suppose that we are working within the integers modulo $p$ where $p$ is some odd prime number. Suppose that $x_0$ is a (nonzero) quadratic residue mod $p$ then there exists some $x_1$ such that $x_1^2 ...
1
vote
3answers
50 views

Fermat primality test $\gcd$ condition and carmichael numbers

Consider the following quote (I read similar thing in a couple of sources but this one illustrates the issue I'm having): By Fermat's Theorem if $n$ is prime, then for any $a$ we have $a^{n-1} = 1 ...
-1
votes
2answers
56 views

Proof that expression is integer [duplicate]

hi guys can you help me with this? Proof that expression is integer $$\frac{(2n)!}{2^nn!}$$
4
votes
2answers
81 views

Find the number of natural number solutions of $a+2b+c=100$

Find the number of natural number solutions of $a+2b+c=100$ I remember something like stars and bars if the equation I change to $a+b_{1}+b_{2}+c=100$ then i get $\dbinom{99}{3}$ ways. If the ...
1
vote
1answer
34 views

Number theory: Is this argument correct and cube question [duplicate]

First of all, is this argument correct? Suppose $m < n$ are integers. Then for every $k \in \mathbb{N}$ $$m + k < n + k.$$ What I did: Suppose that $m + k \ge n + k$, the by the cancelation ...
3
votes
0answers
84 views

What is the least prime $p$, such that $[p-1000,p+1000]$ does not contain a prime $\ne p$?

I am looking for the least prime number $p$, such that the interval $[p-1000,p+1000]$ contains no prime except $p$. In other words, the prime nearest to $p$ has a distance $>1000$ to $p$. I found ...
0
votes
1answer
20 views

What's the condition for (x+kp) and pq being coprime?

Suppose $p$ and $q$ are large primes and $N=pq$. $x$ is an arbitrary integer in $\mathbb{Z}_p$ and $k$ is a random integer. Then what is the condition for $k$ (suppose $x$ is fixed) such that ...
0
votes
0answers
23 views

Do UF+PNT+SMO+GRH imply SOC?

The title may sound esoteric, but let's make it explicit. Suppose that the conjunction of unique factorization (UF, still open), prime number theorem (PNT, proved by Yoshikatsu Yashiro), Strong ...
0
votes
1answer
73 views

Is an algorithm to find all primes up to $n$ that runs in $O(n)$ time fast?

I kindly ask you if it is useful or fast for a prime number generator to run in $O(n/3)$ time? I believe I have a way to generate all $P$ primes up to $n$, quickly and neatly, in $P$ comparisons and ...
2
votes
2answers
26 views

Calculate cycle length

let $a, n, m \in \mathbb{Z}$ and $i\in\mathbb{N}$ and $$(a+in) \mod m$$ Is there a closed way to tell for what $i$ the congruence begins to cycle? Thanks
0
votes
1answer
37 views

Solvability of $a \equiv x^2 \mod b$

Suppose you want to prove that $\exists x \in \mathbb{Z}$ with $a \equiv x^2 \mod b$. Write $b = \prod_{i = 1}^{k} p_i^{e_i}$, the prime factorisation of $b$. Why is the equivalent with finding ...
1
vote
1answer
42 views

Sum of powers of a matrix with primitive polynomial modulo $2^{r}$

I need to prove an statement in the matrix form, which leads to the following equality modulo $2^{r}$. Which I couldn't prove but with computer simulation for lots of primitive polynomial, it seems to ...
1
vote
1answer
20 views

Avoiding range of a bivariate integer function or diophantine function

I'm trying to find a function or sequence (of integers) which avoids all the range values of the following integer function where $x,y \in \{0,1,2,...\}$ and $f(x,y)=5+23*x+7*y+30*x*y$. Does anyone ...
-3
votes
0answers
27 views

Considering only integers, answer the following questions:

Considering only integers, answer the following questions: (i) A number N = 21P53Q4. The number of ordered pairs (P,Q) such that the number ‘N’ is divisible by 44 is? (ii) A number N = 73P4961Q0. ...
3
votes
1answer
49 views

Product of a Finite Number of Matrices with a Cosine Entry

Does any one know how to prove the following identity? $$ \mathop{\mathrm{Tr}}\left(\prod_{j=0}^{n-1}\begin{pmatrix} 2\cos\frac{2j\pi}{n} & a \\ b & 0 \end{pmatrix}\right)=2 $$ when $n$ is ...
1
vote
1answer
40 views

Proving $x^2 - x = y^5 - y$ is a hyperelliptic curve

Greetings to one an all! How can we prove the curve "$x^2 -x = y^5-y$" is a hyperelliptic curve? Is a hyperelliptic curve the same as a hyperbolic elliptic curve or are there any differences?
1
vote
5answers
79 views

Is there a method to calculate large number modulo?

Is there a (number theoretic or algebraic) trick to find a large nunber modulo some number? Say I have the number $123456789123$ and I want to find its value modulo some other number, say, ...
2
votes
0answers
25 views

Application of Legendre, Jacobi and Kronecker Symbols

Legendre, Jacobi and Kronecker Symbols are powerful multiplicative functions in ...