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)

3
votes
1answer
46 views

Show $\sum\limits_{b=0}^{p-1}\left(\frac{b}{p}\right) = 0$

Show $\sum\limits_{b=0}^{p-1}\left(\frac{b}{p}\right) = 0$ The resources I have consulted said to use the fact that the number of quadratic residues $\text{mod } p$ is $\frac{p-1}{2}$ but I have no ...
0
votes
2answers
47 views

Decimals and Rational numbers

How do you prove: Q1) Why is every rational number (say m/n, where m and n are both positive integers) either a terminating or a repeating decimal? Q2) Why is every repeating decimal (or terminating ...
2
votes
1answer
50 views

smallest element order $p$ in $\mathbb Z^*_{p^2}$

I would like to write an efficient algorithm to find the smallest element of order $p$ in $\mathbb Z^*_{p^2}$, where $p$ is a prime number. Therefore I calculate $a^{p-1} \pmod{p^2}$ for every ...
0
votes
2answers
113 views

Solving a Linear Diophantine Equation

A Linear Diophantine Equation is of the following form: $Ax+By+C=0$, where $x_1 \leq x \leq x_2$ and $y_1 \leq y \...
2
votes
2answers
38 views

Summing powers of complex root of unities gives 0

I have a question regarding a proof. Let $z_N$ denote the complex N'th root of unity, from which we have the identities $(z_N)^n=1$ $\sum_{i=0}^{N-1}{(z_N)^i}=0$ Now let $N=r\cdot t$ and let $H^\...
5
votes
1answer
159 views

When is the next palindrome?

Okay, this is more just for fun than anything else. I'm driving in my car today, (true story) and my odometer is about to hit $81,818$. So, being a math nerd and all, I immediately see the pattern ...
2
votes
0answers
40 views

Does a random binary sequence almost always have a finite number of prime prefixes?

Does a random binary sequence almost always have a finite number of prime prefixes? Specifically, let $x = \sum_{1 \le i}{2^{-i} \cdot x_i}$ with $x_i \in \{0,1\}$ be a random real in $[0,1)$, $X_i = ...
4
votes
1answer
98 views

Some questions on the formation of the BSD conjecture

I'm quite curious how Birch and Swinnerton-Dyer formed their famous conjecture in the beginning of 1960s. I read some papers of Birch and Swinnerton-Dyer, as well as some papers of Tate and several ...
4
votes
1answer
98 views

Existence of $\{a_{n}\} $ and $\{b_{n}\}$ such that $a_{n}(a_{n}+1)|(b^2_{n}+1)$

Show that: there exist two sequences $\{a_{n}\}$ and $\{b_{n}\}$ that are monotonically increasing (or $a_{n+1}>a_{n},b_{n+1}>b_{n},\forall n\in N^{+}$) and for any positive integer $n$ $$a_{...
1
vote
2answers
57 views

A stricter Fermat's little theorem

By Fermat's little theorem we know that $a^{p-1} \equiv 1 \pmod{p}$ for all primes p. But it is often possible to find $x$ such that $a^{x} \equiv 1 \pmod{p}$ and x < p - 1. Is there anyway to ...
0
votes
1answer
74 views

Can we not apply the Hensel Lifting Lemma in this case?

Check if the equation $x^2=-1 \text{ in } \mathbb{Z}_2$ has a solution, and if it has, calculate the three first positions of the solution. So, we are looking for a solution $\pmod 2$, one solution $\...
0
votes
2answers
88 views

Prove that if $p$ is a prime and $k$ is an integer, there are two integers $x$ and $y$ that satisfy $x^{2} + y^{2} + k \equiv p$ [closed]

Prove that if $p$ is a prime and $k$ is an integer, there are two integers $x$ and $y$ that satisfy $$ x^2 + y^2 + k \equiv 0 \pmod p. $$
1
vote
1answer
129 views

Distance between powers of 2 and 3

As we know $3^1-2^1 = 1$ and of course $3^2-2^3 = 1$. The question is that whether set $$ \{\ (m,n)\in \mathbb{N}\quad |\quad |3^m-2^n| = 1 \} $$ is finite or infinite.
2
votes
2answers
79 views

Chinese Remainder Theorem RSA

I want to solve the following modular quadratic equation: $x^2 \equiv 188 \pmod {437}$ using the fact that $437$ can be factorized by the primes as: $19⋅23$. So far I have done: $$x^2 \equiv 188 \...
4
votes
2answers
136 views

The Conjecture That There Is Always a Prime Between $n$ and $n+C\log^2n$

Let $n$ be 113. Use $n+C\log^2n$ to find the next consecutive prime or at least approximately how far away it is. Will you show me how to work this out step by step to show me how to use this formula? ...
1
vote
3answers
109 views

Finding if a number is prime by looking at the sum of their digits

Take a number $N = \overline{abcdef...}$ where $a, b, c, d,e,\dots$ are the digits of $N$. Let $k$ be the sum of those digits : $a+b+c+d+e+... = k$ If $k$ is any of ${1, 2, 4, 5, 7, 8 }$ then $N$ ...
2
votes
0answers
74 views

When is “being a linear algebraic $k$-group” preserved?

Let $G$ be a linear algebraic group over a field $k$, with Char$(k)=0$. What "group-theoretical operations" preserve the property of "being a $k$-linear algebraic group"? For example When ...
1
vote
1answer
81 views

Number of answers of equation amongs odd natural numbers

How many answer The following Equation has, in set of odd natural numbers? $x_1+x_2+...+x_k=n$, $k \equiv^2 n$ Solution: Comb ( [(n+k)/2]-1, k-1), comb means combination. how we get this?
1
vote
2answers
140 views
1
vote
0answers
168 views

IMO 1983 Solution - Day 1 Problem 3

The questions goes as follows: Let $a$ , $b$ and $c$ be positive integers, no two of which have a common divisor greater than $1$. Show that $2abc - ab - bc - ca$ is the largest integer which cannot ...
1
vote
1answer
54 views

How to compute this probability: uniform distribution of two random variables

Let $p$ be a prime number. Let $i,j \in \{1, \dotsc, p-1\}$ be fixed numbers. Let $A$ and $B$ be two random variables, where $A \in_{u.a.r} \{1,...,p-1\}$ and $B \in_{u.a.r} \{0,...,p-1\}$. ...
1
vote
1answer
38 views

Number of different vectors.

Let's say that I have a vector with 6 elements. I put two wedges in the vector, i.e., at position 2 and position 6, for instance. And when I say put a wedge, it means... for every time you traverse (...
0
votes
2answers
57 views

If $c | ab$, then $c | a$ or$ c | b$

I need help proving/disproving the implication, If $c | ab$, then $c | a$ or $c | b$ So far, I got Assume $c | ab$ then $ab= cl$ for some integer $l$ Now what should my next step be?
4
votes
1answer
142 views

A number theory puzzle

I recently came across the following number theoretic puzzle. Suppose I've infinitely many cards, each with a natural number written on it. Given any $n\in \mathbb N$, the number of cards which have a ...
6
votes
1answer
178 views

Why is $2^{16}=65536$ the only power of $2$ less than $2^{31000}$ that doesn't contain the digits $1$, $2$, $4$ or $8$ in its decimal representation?

$65536$ is the only power of $2$ less than $2^{31000}$ that does not contain the digits $1$, $2$, $4$ or $8$ in its decimal representation. http://en.wikipedia.org/wiki/65536_%28number%29
2
votes
1answer
76 views

Closed form for $\sum_1^\infty 1/p^n$

I was wondering if there are some studies on closed forms for the sum $$\sum_{p \in \mathbb{P}}^\infty \frac{1}{p^n},$$ where $\mathbb{P}$ denotes the set of prime numbers. Obviously I know that ...
2
votes
3answers
47 views

Congruence between binomial coefficient and integer part.

If $p$ is a prime number , prove that $\forall n \in \mathbb{N}, n\geq p:$ $$\binom{n}{p} \equiv \Bigg[\frac{n}{p}\Bigg] (\text{mod }p)$$ where [ ] is the integer part i´been trying this problem ...
0
votes
2answers
58 views

How to show the congruence involving the divisor function

Prove that if $n \in \mathbb{N}$; $n \equiv -1$ $(mod 24)$ $\Longrightarrow $$ \sigma(n) \equiv 0$ $ (mod 24) $ where $\sigma $ is the divisor function. my try: if $n \equiv -1$ $(mod 24)$ ...
0
votes
2answers
54 views

The Greatest Prime Less Than $n$

Let $n$ be any natural number greater than 2. Let $l$ be the greatest prime less than $n$. When $n$=3, $l$=2. When $n$=10, $l$=7. When $n$=25, $l$=23. What is the relationship between $n$ and $l$? ...
4
votes
1answer
92 views

Showing $\mathbb{Z}+\mathbb{Z}\left[\frac{1+\sqrt m}{2}\right]$ is a Euclidean domain

Does anyone know an elementary proof for the following proposition? It is stated without proof in my textbook: Let $m$ be a negative squarefree integer with $m \equiv 1 \pmod 4$. Then the integral ...
0
votes
2answers
26 views

Is proof by modular arithmetic appropriate in this syntax?

I have a question which asks: Prove there are no integer solutions for the equation: $$4x = y^2 +1 $$ To prove, lets take $\pmod4$ of both sides, such that: $$ 4x\pmod4 = (y^2 +1)\pmod4$$ $$ \...
1
vote
2answers
80 views

Twin Prime Constant

How would one prove that the twin prime constant $$C_2 = \prod_{p > 2}1-\frac{1}{(p-1)^2} > 0$$ Simply computing the product for a large number of terms isn't rigorous, and simply establishes ...
0
votes
1answer
67 views

Exact Equivalence of Legendre's Conjecture Impossible?

If the upper bound for the prime gap above $n$ is such that $n$+4$\sqrt{n-1}$$\geq p$, where $n$ is any given natural number and $p$ is the next prime after $n$, then Legendre's conjecture is true. If ...
26
votes
1answer
566 views

Prove that both $x+y$ and $xy$ are rational, under some conditions

As a result of the answer I got for this question - Irrational solutions to some equations in two variables - I was wondering if the next statement is always true: Let $x,y$ be real, irrational ...
2
votes
0answers
35 views

Solutions $\pmod {p^n}$

We have a solution $x_0 \pmod 7$ of $x^2 \equiv a \pmod 7$. To find a solution $\pmod {7^2}$, we are looking for $x_1 \in \mathbb{Z}$ such that $$x_1^2 \equiv 2 \pmod {7^2} \text{ such that } x_1 \...
1
vote
5answers
93 views

How did we find the solution?

In my lecture notes, I read that "We know that $$x^2 \equiv 2 \pmod {7^3}$$ has as solution $$x \equiv 108 \pmod {7^3}$$" How did we find this solution? Any help would be appreciated!
-2
votes
2answers
124 views

lowest denominator to lie between to rational numbers.

What's the lowest $ m\in \mathbb {N} $ such that the exists an $ n $ with $1/3 >\frac {n}{m}>33/100$? note that there used to be a typo in the inequality which gives the opposite sign I'm on my ...
0
votes
1answer
61 views

Make whole array as zero

Given an array of N elements some of which are positive and some are negative now some positive valued elements can give their value to negative valued elements.Now we need to make whole array as zero ...
2
votes
2answers
117 views

When is a sum of consecutive roots of unity an integer

Let $\xi \neq 1$ be an $n$th root of unity. When is a sum of the form $$ 1+\xi+\xi^2+\ldots+\xi^r, \quad 1 \leq r \leq n-1, $$ an integer? What are the possible integers? I suspect that the answers ...
2
votes
0answers
55 views

Can one prove the divergence of $\sum \frac{1}{p}$ by the absolute convergence criterion of infinite products?

Euler proved this celebrated theorem that $\sum \frac{1}{p}=\infty$ by using the product formula that $\displaystyle \zeta (s)=\prod \left( \frac{1}{1-p^{-s}}\right)$. Now I thought of another proof(...
2
votes
1answer
57 views

Divisibility Property

I am trying to justify the following result: Let $p,q$ be integers such that $GCD(p,q) = 1$. Then for all $n \in \mathbb{N}$ exists an integer $j_n$ such that $q^{j_n}t = t \ (mod \ p^{2n+1}), \ \...
8
votes
5answers
924 views

Is $x^{1-\frac{1}{n}}+ (1-x)^{1-\frac{1}{n}}$ always irrational if $x$ is rational?

Let $x$ be rational with $0<x<1$ and let $y$ be the rational defined by $y = 1 - x.$ Let $n$ be any natural number with $n>2.$ Then I want to prove that $$x^{(1-1/n)}+ y^{(1-1/n)}$$ will ...
1
vote
1answer
60 views

How to write a general proof to prove that for all $m$, $m^n \geq n^m$

After proving $m^n \geq n^m$ for several values of $m$, it can be inferred that for every $m$ there's a $k$ such that if $n \geq k$, $m^n \geq n^m$. In other words, this can be generalized as: For ...
4
votes
1answer
201 views

Group of Units in Cyclotomic Integers

I'm trying to show that for any $p$-th root of unity $\zeta$, where $p$ is an odd prime, we have $\mathbb{Z}[\zeta]^{\times} = \left<\zeta\right>\mathbb{Z}[\zeta + \zeta^{-1}]^{\times}$. ...
0
votes
1answer
206 views

Number of ways to make n digit number?

Given M digits which are between 1 to 9, Find the number of ways to form N digit number, by repeating one or more given digits such that each of M digits are present in N digit number at least once. ...
2
votes
0answers
121 views

Game theoretical approach to other branches of mathematics

Are there some methods and ideas derived from game theory that are successfully applied to better (or more intuitively) understand theorems and proofs or tackling problems from other areas of ...
1
vote
1answer
151 views

Integers (strictly) between 0 and 1 form the basis of transcendental number theory?

In a MathOverflow comment on the question of "What is the most useful non-existing object of your field?", an answer is given A number which is less than 1 and greater than 1. Which elicited a ...
1
vote
1answer
110 views

Can $\sqrt{a}^\sqrt{b}$ be rational if $\sqrt{a}$ and $\sqrt{b}$ are irrational?

Let $a$ and $b$ be rational numbers, such that $\sqrt{a}$ and $\sqrt{b}$ are irrational. Can $\sqrt{a}^\sqrt{b}$ be rational? I found examples, where the irrational power of an irrational ...
2
votes
2answers
83 views

Perfect square then it is odd

I have tried several values by trail and error and I concluded the following fact. 'if the $S = 4x^5-4x+1$ is perfect square for some integer $x$, then square root of $s$ is always an odd integer' ...
0
votes
0answers
55 views

Continuation of the Zeta Function

I already showed that für $\sigma >1$, $$\zeta (s) = \frac{1}{s-1} + \frac{1}{2} + \sum_{j=1; 2\mid j+1}^{k-1}\left( \prod_{i=0}^{j-1}(s+i) \right) b_{j+1}(0) - \left( \prod_{j=0}^{k-1}(s+j)\right) ...