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)

4
votes
3answers
109 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 ...
-4
votes
1answer
59 views

Proof that ${2n \choose n}= \frac {1\cdot3\cdot5\cdots(2n-1)}{n!}2^n$ [closed]

HELP ME WITH THIS EXERCISES.. Proof for induction that $${2n \choose n}= \frac {1\cdot3\cdot5\cdots(2n-1)}{n!}2^n$$
1
vote
3answers
46 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
53 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 ...
0
votes
0answers
14 views

Scope of expressions which determine whether an integer can be resolved into 2 triangles [closed]

It is straightforward to show that for any prime P of the form 4n+1, (P-1)/4 +kP can be resolved into the sum of two triangles if and, only if, k can be, and similarly for all primes of the form 4n+3, ...
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
22 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
71 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 ...
1
vote
2answers
25 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
39 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
47 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
39 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
77 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
24 views

Application of Legendre, Jacobi and Kronecker Symbols

Legendre, Jacobi and Kronecker Symbols are powerful multiplicative functions in ...
4
votes
1answer
65 views

Elementary proof that $\sum_{k=1}^{\infty}{\frac{1}{m^{k^2}}}$ is irrational (for any integer $m > 1$)

I used similar technique as Fourier's proof of irrationality of $e$ https://en.wikipedia.org/wiki/Proof_that_e_is_irrational to show that this series is indeed an irrational number but I was wondering ...
8
votes
1answer
84 views

are these two continued fractions equivalent?

I would like to pose the following conjecture.Given $$\phi(q) =\cfrac{1}{1-q+\cfrac{q(1-q)^2}{1-q^3+\cfrac{q^3(1-q^2)^2}{1-q^5+\cfrac{q^5(1-q^3)^2}{1-q^7+\ddots}}}}$$ and ...
-3
votes
0answers
72 views

Does number 1 really exist? [closed]

1) As per decimal system when we start numbering we can start from 0.000000.....1 or the number before 1 ie .99999999999......9 so since .00000... can be infinity we dont even start with the first ...
3
votes
2answers
75 views

Finding the missing digits of $23!$

It is given $23!=2585201xy38884976640000$. Now it is required to find the value of $x$ and $y$. I know I could find it by using divisibility rules and solving simultaneous equations. Is there any ...
3
votes
0answers
52 views

The form of the zeta function of an elliptic curve over a finite field

I seek a (very) elementary proof that the zeta function of an elliptic curve $E$ over $\mathbb{F}_q$ has the form $$Z(T)=\frac{1-aT+qT^2}{(1-T)(1-qT)}.$$ Something tedious and computational making use ...
-4
votes
0answers
29 views

Non trivial non prime or maximal ideals [on hold]

Let R = $\mathbb{Z}$ x $\mathbb{Z}_{80}$ A) Determine a maximal ideal of R B) Determine a prime ideal that is not maximal c) Determine a nontrivial ideal of R that is neither prime or maximal ...
1
vote
1answer
29 views

Are the Bernoulli denominators always divisible by these corresponding primes?

I was wondering whether it has been proven/disproven yet or at least conjectured that the bernoulli denominator of $B_{2n}$ is divisible by $2n+1$ if and only if $2n+1$ is prime? If not, must the ...
1
vote
1answer
39 views

Estimates for $1/\zeta(s)$

Recently I am reading Stein's Complex Analysis, and he is going to prove the prime number theorem after estimating the value $1/\zeta(s)$. However, I don't understand the technical details of the ...
2
votes
0answers
33 views

Finding primes using the Fibonacci sequence in modular form

I was wondering if the following is already a known result in mathematics. I have tested it and it seems to work every single time. If I write the Fibonacci sequence in $\bmod (a)$ form and it ...
1
vote
1answer
91 views

How to solve special type of Diophantine equation

I am so excited to learn finding integer solutions of the equation $x^2 -y^5 = x-y$. I just found few solutions by plugging various integers in place of $x$ and $y$. But, I need a permanent method or ...
1
vote
3answers
25 views

Minimize given LCM

Find the smallest possible value of $n_1+n_2+\cdots+n_k$ such that $LCM(n_1,n_2,\ldots,n_k)=(2^2)(3^3)(5^5)$. Note that $k$ is not fixed. I know the answer should be $k=3$, $n_1=2^2$, $n_2=3^3$, and ...
1
vote
1answer
82 views

regularization of sum $n \ln(n)$

I was testing out a few summation using my previous descriped methodes when i found an error in my reasoning. I'm really hoping someone could help me out. The function which i was evaluating was ...
1
vote
1answer
37 views

Induction Proof - Primes and Euclid's Lemma

I'm having some trouble with this proof. Here's the question: Use mathematical induction and Euclid's Lemma to prove that for all positive integers $s$, if $p$ and $q_1, q_2, \dotsc, q_s$ are prime ...
2
votes
1answer
51 views

Which power of an integer matrix is identity modulo $p^\alpha$?

I've read this question about identity power of an integer matrix. But how about power of a matrix modulo $p^\alpha$. $$A^m \equiv I \pmod{p^\alpha} $$ How can I find the minimal $m$ that the above ...
5
votes
5answers
86 views

Decomposing an integer into primes raised to different powers

The number $711000000$ can be written as $79^1 \times 2^6 \times 3^2 \times 5^6$. How are these numbers found? I guess the more general question is - given $n \in \mathbb Z $, how can you ...
2
votes
2answers
150 views

Solving the equation $ x^2-7y^2=-3 $ over integers

I'd like to solve the following Pell equation: $$ x^2-7y^2=-3 $$ Where $x$ and $y$ are integers. I applied the usual procedure, which avoids continued fractions: The two minimal positive integer ...
4
votes
2answers
64 views

Ordering of natural numbers

Show that it is possible to arrange the numbers 1, 2, . . . , n in a row so that the average of any two of these numbers never appears between them. Hint: Show that it suffices to prove this fact ...
-4
votes
0answers
66 views

What inconsistencies/ fallacies do techniques used in assigning -1/12 to the infinite sum “1+2+3+4+…” contain? [closed]

It would be helpful if the downvoters could communicate the reason for downvoting the question. I think I have clarified the question adequately below. If I am missing something, requesting you to ...
-2
votes
1answer
44 views

Fi Binary Number [closed]

A Fi-binary number is a number that contains only 0 and 1. It does not contain any leading 0. And also it does not contain 2 consecutive 1. The first few such number are 1, 10, 100, 101, 1000, 1001, ...
7
votes
2answers
122 views

Arithmetic Derivatives: Arithmetic Logarithmic Derivative Problem

In Calculus, whenever we see a constant and want to take the derivative of it, it always is 0. However in Number Theory, we have something called the arithmetic derivative in which we can ...
7
votes
1answer
46 views

Orbits of the $\text{SL}(n,\mathcal{O}_K)$-action on $\mathbb{P}^{n-1}(K)$ for a number field $K$.

I was reading some notes of Keith Conrad where he proves that the number of orbits of the $\text{SL}(2,\mathcal{O}_K)$-action on $\mathbb{P}^{1}(K)$ for a number field $K$ is precisely the class ...
3
votes
1answer
43 views

Chiese Remainder Therorem : No solutions

I have asked a similar question before on Chinese Remainder Theorem. Now concepts are getting clear. Thinking of a possible case where there are no solutions. Suppose the question is ...
0
votes
1answer
52 views

Bowers array notation : $f_{\omega^\omega}(n)\approx [n,…,n]$ ($n$ times)

I learnt at this site that $$\large f_{\omega^\omega}(n)\approx \underbrace{[n,...,n]}_{n\ n's}$$ For a simular approximation $$\large f_{\omega^2}(n)\approx \underbrace{n\rightarrow ...
2
votes
1answer
75 views

X raised to power-X raised to power-3 equals to 3.

The question is what are the possible values of $x$ when we have $$x^{x^3} = 3$$ (that is $x^3$ in the exponent itself and not $x*3$). I solved one answer by guessing that $x = \sqrt[3]3$. My work ...
4
votes
1answer
82 views

Integer solutions to $x^2=2y^4+1$.

Find all integer solutions to $x^2=2y^4+1$. What I tried The only solutions I got are $(\pm 1 ,0)$, I rewrote the question as : is $a_{n}$ a perfect square for $n>0$ were $$a_0=0,\quad ...
5
votes
1answer
55 views

The Sieve of Eratosthenes as sum of square waves

I wrote this equation, that is a way to represent the Sieve of Eratosthenes: $-1+\sum\limits_{i=2}^{\infty} ( 2 \left \lfloor \frac {x}{i} \right \rfloor - \left \lfloor \frac {2x}{i} \right \rfloor ...
0
votes
1answer
16 views

Hilbert Symbol over $\mathbb{R}$ (bilinearity)

Let $\mathbb{R}$ be the field of the reals and let $a,b,c \in \mathbb{R}^{\times}$. As you probably know, the Hilbert symbol over any field $K$ is defined as: $$(\frac{a,b}{K}) = 1 \text{ if } \exists ...
0
votes
0answers
30 views

Unique extension of the absolute value

Let $(K,u)$ be a complete valued field, $u$ be its discrete absolute value (corresponds to a discrete valuation on $K$), then: ($\ast)$ Let $E/K$ is a finite separable field extension, then the ...
-2
votes
0answers
43 views

Number Theory - Factors [closed]

I have come up with a number theory problem from SL Olympiad. At most how many distinct factors of 2009 to the power 2010 can be selected such that none of the selected factors divides another ...
2
votes
2answers
62 views

percentage of integers such that $n^4 \pmod{16} \equiv 1$?

How do I find the percentage of numbers $n$ in the list $1^4, 2^4, ... 1000^4$ such that $n \pmod{16} \equiv 1$? I know that for any $x$, if $x \pmod{16} \equiv 1$, then $x^n \pmod{16} \equiv 1$, so I ...