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)

5
votes
1answer
66 views

Average prime value in n factorial.

I was wondering about the (weighted) average prime value in the factorisation of $n!$. $\\$ If we call $f(n)$ the average prime value in $n!$, then $f$ seems to increase rather linear. Is there a ...
2
votes
1answer
46 views

What is the period of $f(x) = x^x \pmod n$?

For $n = 2$, $f(x)$ is the sequence $1, 1, 0, 1, 0, 1, 0, 1, 0, \ldots$ (period $2$). For $n = 3$, $f(x)$ is the sequence $1, 1, 1, 0, 1, 2, 0, 1, 1, 0, 1, 1, 2, 0, 1, 1, 0, 1, 2, 0, 1, 1, \ldots$ ...
2
votes
2answers
90 views

Is $\frac{1010103010101}9$ prime or composite?

$1010103010101$ obviously divisible by $9$. Is $\frac{1010103010101}9$ prime or composite? The answer would be obtained without using WolframAlpha
3
votes
1answer
36 views

Function field, finite extension, isomorphism implies isomorphism?

Let $A$ be a function field in $1$ variable over $\mathbb{C}$, and let $B$ be a finite extension of $A$ of degree $[B : A]$. If $B \cong \mathbb{C}(x)$ over $\mathbb{C}$, then does it necessarily ...
0
votes
1answer
23 views

Proving $o(g^r) = n / \gcd(n,r) $? [duplicate]

Let $G$ be a group, and let $g \in G$ be an element of order $n \in \mathbb{N} \setminus \{0\}$. Prove that for all $r \in \mathbb{Z}$ we have $$ o(g^r) = \frac{ n}{\gcd(n,r)} $$ where $o(g^r)$ means ...
4
votes
1answer
48 views

$a(x)$, $b(x) \in \mathbb{C}(x)$ and $b(x)^2 = a(x)^3 + 1$ implies $a(x)$, $b(x)$ constant?

If $a(x)$, $b(x) \in \mathbb{C}(x)$ and $b(x)^2 = a(x)^3 + 1$, then does it necessarily follow that $a(x)$ and $b(x)$ are constant? Edit. To clarify, $\mathbb{C}(x)$ is the field of rational ...
0
votes
1answer
45 views

Use Fermat factorization to factor $809009\ldots$

Use Fermat factorization to factor $809009\ldots$ So far I have: \begin{align} \sqrt{809009} & = 889.449 \\ & = 890 \\[6pt] \sqrt{890^2 - 809009} & = 130\ldots ∉ \mathbb Z \\[6pt] ...
1
vote
0answers
48 views

Are you sure the following is true or not.:$(0.\overline{9}=1 )$ [duplicate]

Are you sure the following is true or not.: $(0.\overline{9}=1 )$ If proven true or false is not.Thank
-3
votes
6answers
68 views

to find the $x$th element in a series like $a_1,a_1,a_2,a_1,a_2,a_3,a_1,a_2,a_3,a_4$

we have say n numbers a1 ,a2,a3,.......aN . let us say that n=5 so numbers are ...
1
vote
1answer
42 views

Let $p$ be a prime. Then for every integer $a$ there is an integer $x$ such that $x^3 \equiv a \pmod p$

Let $p$ be a prime. Then for every integer $a$ there is an integer $x$ such that $x^3 \equiv a \pmod p$. I prove it using a Fermat little’s theorem but I want help with counterexample. We know that ...
4
votes
1answer
36 views

Criterion for the integral closure of an domain in a finite field extension being a finitely generated algebra

$A$ is an integral domain, $K=\operatorname{Frac}A$, $L/K$ finite field extension (not necessarily separable), $B$ is the integral closure of $A$ in $L$. Question: with some extra conditions on $A$, ...
-1
votes
0answers
22 views

if p and q are distinct primes and n=p q then there is a primitive root mod n [duplicate]

if p and q are distinct primes and n=p q then there is a primitive root mod n could you help me with counterexample I prove it and I find this statement is false , I try many example and all of them ...
1
vote
2answers
34 views

How to calculate $x$ in $19^{93}\equiv x\pmod {162}$?

I have to calculate $19^{93}\equiv x\pmod {162}$. All I can do is this,by using Euler's Theorem:- $19^{\phi(162)}\equiv1\pmod{162}$ So,$19^{54}\equiv1\pmod{162}$ Now,I have no idea how to reach ...
1
vote
2answers
41 views

Prove that $p|1+2(p-3)!$

Prove that $p|1+2(p-3)!$ I know the wilson's theorem and started with that but I reach a stage where I am not able to solve. $1+(p-1)!= M(p)$ $=1+(p-1)(p-2)(p-3)!= M(p)$ $=1+ (p^{2}-3p+2)(p-3)! ...
1
vote
0answers
22 views

If p>2 is prime and r is primitive root mod p then r^((p-1)/2) == -1 (mod p)

If p>2 is prime and r is primitive root mod p then r^((p-1)/2) == -1 (mod p) Could you help me this statement is true or false ? I do it by fermat little theorem and I find it equal + - 1(mod p) I ...
1
vote
0answers
54 views

Is this a new twin prime sieve method? Any information or comments is very appreciated.

I'm studying the twin prime numbers. Instead of sieving prime numbers, I found this method to sieve $\{x: x \neq \pm 1 \text{( mod $p$)}, x \in \mathbb{N}, p \le p_i\}$, so that $(x-1,x+1)$ will be ...
-1
votes
1answer
29 views

If $a$ is odd then$(a^2)^n \equiv1$ (mod $2^{n+1}$) for all $n \geq 1$

If $a$ is odd then $(a^2)^n \equiv 1 (mod 2^{n+1})$ for all $n \geq 1$ I know it is false statement when I prove it by induction but could you help me give me counterexample show it is false I try ...
2
votes
1answer
53 views

There are at most finitely many square-free integers $d\not\equiv 1\pmod{4}$ such that $\mathbb{Q}(\sqrt{d})$ is a Euclidean field

My book's exercise is about proving that there are at most finitely many square-free integers $d\not\equiv 1\pmod{4}$ such that $\mathbb{Q}(\sqrt{d})$ is a Euclidean field (with respect to the norm). ...
3
votes
2answers
57 views

Given $x^3$ mod $55$, find its inverse

So i am wondering how i can figure out what the functional inverse of $x^3$ mod $55$ is. I can only assume it is $x^{1/3}$ mod $55$ but i am not sure if that is the form i should keep it in
10
votes
0answers
87 views

Is there a clever way to find a smaller number that produces the Euclidean algorithm of given length?

Is there a simple way to tell if for a given $n$ there is $m$ such that the Euclidean algorithm on $n,m$ runs for a given number of steps, and/or a way to find $m$ efficiently (other than testing all ...
0
votes
0answers
23 views

Norm of ideal belongs to the ideal [duplicate]

Suppose that $D$ is any number ring (i.e. $D=\mathbb Q(\alpha), \alpha \in \mathbb C$). Let $I$ be any ideal of $D$. Show that $N(I)=|D/I|$ belongs to $I$. How to start? is there a specific fact will ...
2
votes
2answers
507 views

What is the average prime numbers we've found till now?

When you count from 0 to 100 you have 25% prime numbers. Till now the largest prime consists of $2^{74,207,281}-1$ numbers. But is known what the average is till now? With average I just mean the ...
2
votes
0answers
29 views

Let $N=3^{1000}\times 2^{200009} +1$. Show that $5^{\frac{N-1}{2}}\equiv -1 \pmod{N}$.

This is showing that 5 is a quadratic non-residue mod N but I don't get why this says it is prime. The question also asks that you say that if p was prime divisor of N what the power of 2 dividing ...
7
votes
0answers
73 views

Which prime factors of $8^{8^8}+1$ are known?

We have the partial factorization $$8^{8^8}+1=(2^{2^{24}}+1)\cdot (2^{2^{25}}-2^{2^{24}}+1)$$ The first factor is $F_{24}$. It is composite, but no prime factor is known. A prime factor of the ...
0
votes
0answers
20 views

Why is conductor of a Dirichlet character the product of conductors of other Dirichlet characters?

Let $n=\prod_{i=1}^np_i^{e_i}$ with $p_i$ different prime numbers and $e_i$ positive integers. Given a Dirichlet character $\chi$ modulo $n$ we can define the characters $\chi_i$ (modulo $p_i^{e_i}$) ...
0
votes
0answers
5 views

Particle moving and dividing on real line, reference to Sierpinsky triangle

Problem: At time $t=0$, a particle is at $x=0$ on the real line. At $t=1$, the particle divides into $2$ and moves one unit to the left and the other moves one unit to right. At $t=2$, each of these ...
7
votes
0answers
59 views

Sum of three consecutive cubes equals a perfect square

I have found this problem in an old German textbook: Find all sets of three consecutive integers such that the sum of their cubes is a perfect square. We can write $$S = (x-1)^3 + x^3 + (x+1)^3 = ...
2
votes
3answers
50 views

How to find open subgroups of finite index in $\mathbb{Q}_{3}^{\times}$?

For purposes of illustrating Local Class Field Theory, let us play with the $3$-adic numbers. I'd like to find some open subgroups of finite index in $\mathbb{Q}_{3}^{\times}$. I know about the ...
1
vote
2answers
31 views

$2^{49}$ ways to choose a set of integers $\leq 50$ with odd sum

Problem: Show that the number of ways one can choose a set of distinct positive integers, each smaller than or equal to $50$, such that their sum is odd, is $2^{49}$. My attempt: Suppose set ...
0
votes
0answers
14 views

Recursive definition of Minkowski ?(x) function

There is a fact that $?(\frac{a+b}{c+d}) = (?(\frac {a}{c}) + ?(\frac{b}{d})) / 2$ if a/c and b/d are adjanced elements of Farey sequence. How to prove it? I don't have any ideas at all.
0
votes
0answers
49 views

Number of solutions to a modular equation of a specific form

I struggle with this Exercise, or at least the part where one should prove how many solutions there are. Simply inserting f=0 contradicts the suggested number of solutions. Let $p$ be an odd ...
3
votes
3answers
119 views

Find all natural numbers $n$ such that $21n^2-20$ is a perfect square.

Find all natural numbers $n$ such that $21n^2-20$ is a perfect square. I have got the following solutions via programming: $n=1,2,3,9,14,43,67$ but how can I find these manually? How can I ...
1
vote
1answer
62 views

Is it known if $\frac{\zeta(3)}{\pi^3}\in\mathbb{Q}$? [duplicate]

Is it known if $\frac{\zeta(3)}{\pi^3}\in\mathbb{Q}$? It is obvious that $\frac{\zeta(2n)}{\pi^{2n}}\in\mathbb{Q}$, but since there is no closed form for the odd values, are we left to be unable ...
0
votes
0answers
16 views

Intuition in understanding Minkowski question mark ?(x) function

There are 3 definitions of Minkowski function: 1) If $[a_0; a_1, ...]$ is a continuous function representation of n 2) Consider the different ways of interpreting an infinite string of bits ...
0
votes
0answers
26 views

For a given non-constant polynomial $f(x)$ with integer coefficients, how many solutions are there to $f(x)\equiv 0 \mod(n)$ where $n$ is composite?

For a given non-constant polynomial $f(x)$ with integer coefficients, how many solutions are there to $f(x)\equiv 0 \mod(n)$ where $n$ is composite? Is there a general way to determine the number of ...
0
votes
0answers
21 views

Number of solutions to $f(x)\equiv 0 \mod(11\cdot 19^{2})$

I have been asked to explain why the number of solutions of the polynomial congruence $f(x)\equiv 0 \mod (11\cdot 19^{2})$ cannot be 121, where $f(x)=x^{10}+10x^{8}-17x+12$. Any ideas?
1
vote
1answer
19 views

Is a divides infinitely many repunits?

Let (a,10)=1 Let n=9k{phi(a)} using eulerphi function k is positive integer. When (a,9)= 1 , 3 it is okay Because 81 and a divides 10^n-1 by Binomial theorem and CRT So a divides (10^n-1)/9 ...
6
votes
1answer
44 views

Solve $2^{99}$ mod $101$

My number theory is a bit rusty, so i am trying to recall how to work this problem out. I know that the euler theorem would state that $2^{\phi(101)} \equiv 1$ mod $101$ But in this case, ...
2
votes
1answer
32 views

If $p>5$ is prime, $2p+1$ is a prime, $\frac{4p+1}{3}$ is prime, $8p+1$ is prime, Then $p \equiv 29 (mod \; 30)$

Assume that $p>5$ is prime, $2p+1$ is a prime, $\frac{4p+1}{3}$ is prime, $8p+1$ is prime. Then I want to prove that $p \equiv 29 (mod \; 30).$ First of all I have to show that $4p+1$ is a ...
0
votes
3answers
60 views

How many roots does this polynomial have in $\mathbb{Z}/91\mathbb{Z}$?

$f(x)=x^8-1$ I know how I would do this problem if the mod wasn't so high. Not sure how to approach this question.
0
votes
1answer
22 views

Fermat's Little theorem (Num Theory) [closed]

How can I compute $31^{1209}\equiv \mod (101)$ using Fermat's Little Theorem?
0
votes
2answers
26 views

Calculate a quadratic irrational from its periodic continued fraction

I have a periodic continued fraction [2; 1, 3] and I want to convert it into a quadratic irrational. Any helps?
0
votes
2answers
28 views

Basic Number Theory (Divisibility)

Not sure where to start. Thank you in advance! Find all positive integers $n$ such that $12$ divides $n$ and $n$ divides $816$.
0
votes
1answer
19 views

Multidimensional Cantor diagonal argument for ordering infinite sets [duplicate]

Cantor diagonal argument is a powerful proof technique. It has been used for a lot of proofs. For instance, it has been used to prove that $|\mathbb{N}| < |\mathbb{R}|$. What can we say about the ...
0
votes
1answer
18 views

Distances between identical strings in a long Vigenere

My queston is "Distances between identical strings in a long Vigenere ciphertext are 18, 30, 12, 12, 18. What is the likely key length"? I'm looking in the book and it has a similar problem that ...
0
votes
0answers
25 views

Uniqueness of sum and multiplication of numbers

so I was writing a program that took two strings and said if they were anagrams or not, and I had this idea of making each character into a number, adding them all and checking if the result was the ...
4
votes
1answer
51 views

Diophantine Equation $x^2+y^2+z^2=c$

$x^2+y^2+z^2=c$ Find the smallest integer $c$ that gives this equation one solution in natural numbers. Find the smallest integer $c$ that gives this equation two distinct solutions ...
8
votes
3answers
146 views

Finding all solutions for $3^c=2^a+2^b+1$

Given the equation: $3^c=2^a+2^b+1$ Find all solutions for $a,b,c$ - given that they are positive integers and $b>a$. Any ideas?
1
vote
1answer
17 views

Reference for table of cubes modulo $m$?

Is there an online table with all the cubes in $(\mathbb{Z}/m\mathbb{Z})$ (with $m$ up to (say) $100$, at least)? I didn't find anything googling it. Thanks.
2
votes
1answer
39 views

Find all $n$ such that $n|1^n + 2^n + 3^n + \cdots + (n-1)^n$ where $n \in \mathbb{Z}^+$.

Find all $n$ such that $$n|1^n + 2^n + 3^n + \cdots + (n-1)^n$$ where $n \in \mathbb{Z}^+$. I don't know how to start. $n = 3, 5$ are simple solutions. Induction seems strange since the divisor ...