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)

1
vote
0answers
10 views

If$ ( \sigma(n) = 2n+1) \rightarrow n$ is odd.

Prove, that if$ ( \sigma(n) = 2n+1) \rightarrow n$ is odd. $\sigma(n) $ should mean the following function: $\sigma(n)= \sum_{d|n, 1 \le d \le n} d$ For example: $\sigma (12) = 1+2+3+4+6+12 = 28$. ...
0
votes
1answer
25 views

Can two cuboids with different side lengths have the same volume and perimeter?

We know that two rectangles with different side lengths cannot have the same area provided their perimeter is the same. But can two cuboids with different side lengths have the same volume and ...
1
vote
1answer
18 views

Check if $n=m^2$ in $\mathbb F_q$

I'm studying elliptic curves in finite fields, and seeing an algorithm to find points of the curve, there's a point in which I have o check if an element $z\in\mathbb F_q$ is a square number, being ...
5
votes
1answer
39 views

weakened version of Dirichlet's theorem - proof without Dirichlet's theorem

Dirichlet's theorem states that arithmetic sequence with first term and common difference relatively prime, contains infinitely many prime numbers. Assume that we only want infinitely many numbers in ...
5
votes
2answers
44 views

Solving polynomial equations using more than radicals

It is well known that one cannot solve every polynomial equation over $\Bbb Q$ using just radicals. In other words, let $A_n = \{x^n - a\mid a \in \Bbb Q\}$, $A = \cup_n A_n$ and $\bar{\Bbb Q}$ the ...
3
votes
0answers
19 views

Numbers having in decimal representation no common digits with all their proper divisors

Let us call a positive integer having in decimal representation no common digits with all its proper divisors "a good number". $54$ is a good number : $1,2,3,6,18,27$ $48$ is not a good number : ...
1
vote
1answer
22 views

Intuitive explanation for this Gamma function identity

Wolfram Alpha says that this result is true: $$\frac{\Gamma(n+1)}{\Gamma(\frac{n}{2}+1)} = \frac{\Gamma(\frac{n}{2} +\frac{1}{2})}{\Gamma(\frac{1}{2})} \times 2^n$$ This implies a curious result for ...
6
votes
1answer
50 views

Carmichael numbers of form $m^3+1$ and Ramanujan's $1729$

While researching for a post on tetranacci pseudoprimes I came across a list of Carmichael numbers, $$C_n = 561,\, 1105,\, 1729,\, 2465,\, 2821,\dots$$ Of course, Ramanujan's taxicab number $1729 = ...
2
votes
1answer
23 views

Why $\ker N_{E/F}$ is a map from $E^{\times}$ to $F^{\times}$?

I am reading the lecture notes. In the end of page 1, it is said that $\ker N_{E/F}$ is a map from $E^{\times}$ to $F^{\times}$. Here $E/F$ is a quadratic field extension. Let $\alpha \in E$ and ...
1
vote
3answers
33 views

How to prove a Fibonacci inequality using Strong Induction?

Using strong induction I am trying to prove that $$F_n \geq \left(\frac{1+\sqrt{5}}{2}\right)^{n-2} \text{ for all } n \geq 2$$ for the Fibonacci Sequence defined by: $F_0 = 0$, $F_1 = 1$, and $F_n ...
0
votes
1answer
17 views

Prove that if $\{1^5,2^5,\ldots, (pq)^5\}$ is a complete residue system mod $pq$, then $\{1^5,2^5,\ldots,p^5\}$ is too, mod $p$

$p,q\ge 2$ are coprime positive integers. Prove that if $\{1^5,2^5,\ldots, (pq)^5\}$ is a complete residue system mod $pq$, then $\{1^5,2^5,\ldots,p^5\}$ is a complete residue system mod $p$. ...
-1
votes
0answers
31 views

Let $p$ be an odd prime, $D$ be an integer not divisible by $p$. show that $x^2 - y^2 = D (\text{mod } p)$ has $(p-1) $solutions [duplicate]

Let $p$ be an odd prime, $D$ be an integer not divisible by $p$. Show that $$ x^2 - y^2 = D \bmod p $$ has $p-1$ solutions Can somebody help with this problem? Thank you!
0
votes
1answer
39 views

Solutions of the Pell Equation $x^2-2y^2=-1$

I am assigned to find solutions to the Pell-type equation. $x^2-2y^2=-1$ So far, I only have $(7,5), (41,29)$ and $(239,169)$. My question is, is there a general formula to find all its solution? ...
2
votes
1answer
13 views

Division of the Binomial Coefficient

Prove that when p is prime, the binomial coefficient p!/(r!)((p-r)!) is divisible by p with r being greater than or equal to 1 and less than or equal to p-1 . Clearly p! is divisible by p so I cant ...
3
votes
0answers
18 views

exponential sum estimate involving Von Mangoldt function

Let $f(x)$ be a polynomial. Define $$ S(\alpha) = \sum_{1 \leq n \leq N} e^{2 \pi i f(n) \alpha}. $$ I was wondering how does one obtain that $$ \left( \int_0^1 S(\alpha) \ d \alpha \right)^2 \leq ...
3
votes
2answers
68 views

How to populate a $0-$line with $1$'s?

I have a line of $n$ $0$'s like this: Zeroth index -->$000...000$ I want to populate the line with $m$ $1$'s with the following rules: (1) They have to occur after the index ...
1
vote
0answers
44 views

Fermat's last theorem generalization

Are there solutions to Fermat's last theorem in transcendental numbers greater than two, for further details please follow the link below: http://www.quora.com/What-is-the-new-Pythagoras-Theorem Let ...
1
vote
3answers
30 views

Prove there exists $m$ and $k$ such that $ n = mk^2$ where $m$ is not a multiple of the square of any prime.

For any positive integer $n$, prove that there exists integers $m$ and $k$ such that: $$n = mk^2 $$ where $m$ is not a multiple of the square of any prime. (For all primes $p$, $p^2$ does not divide ...
4
votes
2answers
53 views

Find a non-trivial solution for the Diophantine Equation $17a^4 + 5b^4 = 35c^4$, or show that no non-trivial solutions exist

This is a problem on my practice exam for number theory, and we haven't had an example like this in class yet. The question is looking for a solution in $\mathbb{Z}$ for $a,b,c \in \mathbb{Z}$. I've ...
0
votes
1answer
10 views

Stern-Brocot tree and relative primality

I'm reading through chapter on Number Theory on "Concrete Mathematics" and there is a snippet about Stern-Brocot tree and I'm trying to understand why exactly all fractions in the tree are ...
4
votes
1answer
40 views

Sum of elements of a finite Field

Let $F$ be a finite field and $i$ an integer. Calculate the sum of all the elements of $F$,each raised to the $i-th$ power. My approach so ...
0
votes
1answer
28 views

Find the increasing function where $g_4 : \mathbb N^4 \to\mathbb N$, $(a, b, c, d) \mapsto 2^{a−1}3^{b−1}5^{c−1}h_4(d)$

A bijection $g_4 : \mathbb N\times \mathbb N \times\mathbb N \times\mathbb N \to\mathbb N$, with $$(a, b, c, d) \mapsto 2^{a−1}3^{b−1}5^{c−1}h_4(d)$$ is constructed, with $h_4(d)$ as an increasing ...
0
votes
1answer
34 views

Find a function h3(c) that will make $ (a, b, c) \mapsto 2^{a−1}3^{b−1}h_3(c)$ a bijection [on hold]

Find a function $h_3(c)$ that will make $$g_3 : \Bbb N × \Bbb N × \Bbb N → \Bbb N, \qquad (a, b, c) \mapsto 2^{a−1}3^{b−1}h_3(c)$$ a bijection. Your $h_3(c)$ should be an increasing function, i.e. ...
6
votes
2answers
42 views

Quadratic Reciprocity

I've been asked to see if $x^2\equiv83$ $(\mathrm {mod} \ 101^{2000})$ has solutions. Now I know $x^2\equiv(\mathrm{mod} \ 101)$ has no solutions since the quadratic reside symbol ...
3
votes
1answer
37 views

why does exist infinite postive $k$, such $\lfloor \frac{n^k}{k}\rfloor$ is odd numbers

Give the postive integer $n>1$, there exist infinite positive integer $k$ such $\lfloor \dfrac{n^k}{k}\rfloor$ is odd Maybe can Use Euler's theorem,$$n^{\phi{(k)}}\equiv 1\pmod k$$ let ...
4
votes
1answer
57 views

Solve in positive integers: $5x^2+6x^3=z^3$

Solve in positive integers: $5x^2+6x^3=z^3$. $x^2(6x+5)=z^3$ If $(x,5)=5$, let $x=5k$. So $k^2(6k+1)=\left(\frac{z}{5}\right)^3$, we're left with solving $6n^3+1=m^3$. If $(x,5)=1$, ...
-3
votes
1answer
40 views

Show that $1^n+2^n+\cdots+(p-1)^n\equiv 0\pmod {\!p}$ [on hold]

Let $p$ be an odd prime, and let $n$ be an integer not divisible by $p-1$. Show that $$1^n+2^n+\cdots+(p-1)^n\equiv 0\pmod {\!p}$$
0
votes
2answers
76 views

Prove that for any prime p, there are integers x and y such that $p|(x^2+y^2+1)$

I asked this question a couple days ago, Show that for any prime $ p $, there are integers $ x $ and $ y $ such that $ p|(x^{2} + y^{2} + 1) $. but as I asked it as a guest, I could not comment on the ...
1
vote
1answer
45 views

show $p$ is divisible by $(x^2 +y^2 +1)$ [duplicate]

Show that, for any prime $p$, there are integers $x$, and $y$ such that $p$ is divisible by $(x^2+y^2+1)$ Can you show me what to start with? do I prove $p$ is divisible by $x^2$ and $y^2$ ...
0
votes
1answer
21 views

calculation a Legendre symbol with reciprocity

evaluate the following Legendre symbol using quadratic reciprocity (295/401) (713/1009) I know that can flip the numbers and reduce because both 401 and 1009 are 1 mod p and so on, but I am ...
-1
votes
3answers
51 views

show that $3^{(p-1)/2} +1$ is divisible by $p$ [on hold]

let $n$ be an integer $>1$, and suppose that $p=2^n+1$ is a prime. Show that $3^{(p-1)/2} +1$ is divisible by $p$ (First show that $n$ must be even)
0
votes
0answers
23 views

Number of representations of sums of four squares?

I was told that multinomial expansion can be used to determine how many representations of four squares a number like 53 has? I have a number theory textbook and have done some googleing neither has ...
2
votes
1answer
55 views

$\displaystyle\prod_{ p\leq x}p\leq 4^{x-1}$ for all real $x\geq2$

How yo prove this? I'm looking the Erdös proof from Bertrand Postulate and there are many things I don't get. Please don't hints, I'm newbie in combinatorics techniques. In the book I don't get how ...
2
votes
1answer
30 views

Proving consecutive quadratic residue modulo p [duplicate]

Let p be a prime with p > 7. Prove that there are at least two consecutive quadratic residues modulo p. [Hint: Think about what integers will always be quadratic residues modulo p when p ≥ 7.]
-1
votes
0answers
22 views

Quadratic residue dependency on $\bmod 4$ [duplicate]

Let $p$ be an odd prime and let $a$ be a quadratic residue modulo $p$. Write a formal proof showing that $−a$ is also a quadratic residue modulo $p$ if and only if $p ≡ 1 \bmod 4$. I sort of ...
1
vote
0answers
32 views

Irreducible Polynomial-Am I doing this wrong?

Ok,this problem might appear a bit trivial but I have some doubts..If it's not a burden take a look and comment! Let $F$ be a finite field of characteristic equal to $p$ and $ƒ(x)=x^p-α$ $∊F[x]$.Show ...
0
votes
2answers
46 views

Smallest odd number n such that $2^n-1$ is divided by twin primes.

This is a problem from Elementary Number Theory by Burton (7th ed.) I am finding the smallest odd number n such that $2^n-1$ is divided by twin primes $p$ and $q$, where $3 < p < q$. I followed ...
1
vote
1answer
35 views

How to find p+q = sum, where p and q are distinct primes?

I have been given $\phi(m)$ and $m = pq$. Because $p$ and $q$ are primes, $\phi(m) = (p - 1)(q - 1)$ So I was able to find that $p+q$ = sum But how do I find $p$ and $q$ after this? The sum is larger ...
1
vote
1answer
14 views

Torus translation is ergodic if and only if the components of the translation vector are rationally independent.

I'm reading Ergodic Theory and Differential Dynamics by Ricardo Mane. There is a theorem in the book that states the following: If x $\in$ $R^n$, the translation L $_{\pi(x)}$: $T^n \rightarrow T^n$ ...
0
votes
1answer
22 views

Question involving DES cryptosystem

This is probably an easy question. Im Assuming whoever can answer this has access to S-boxes and P boxes etc. Suppose the input to a round of DES is $1010101010......10101010$. (64 bits) Suppose ...
0
votes
1answer
31 views

Number Theory, using order of integers

I have $k = 37$ and $m = 101$ How do I find $a$, given the value of $a^k \bmod m$? I think this has to do with order of integers.
3
votes
1answer
32 views

Show that $α$ is a perfect square in the quadratic integers in $\mathbb Q[\sqrt{d}]$

Question: Suppose that $\mathbb Q[\sqrt{d}]$ is a UFD, and $α$ is an integer in $\mathbb Q[\sqrt{d}]$ so that $α$ and $\barα$ have no common factor, but $N(α)$ is a perfect square in $\mathbb Z$. How ...
0
votes
1answer
24 views

Largest common divisor

Show that each common divisor $c_1 , \ldots , c_n \in \mathbb{Z}$ divides their largest common divisor. Use subgroups of the group $ \mathbb{Z}$. Could somebody help me? Please
0
votes
0answers
11 views

Torelli Shanks Algorithm - Repeated Squarring Method

This algorithm is using when you want to find a square root of a number in a given moduli. I can't see the idea behind this algorithm, so can someone explain it in a simple way?
0
votes
0answers
30 views

An interesting property of curves $V:$ $x^3$ + $y^3$ = A$z^3$

Let $V$ be the elliptic curve V: $x^3$+ $y^3$ = A$z^3$ where A > 2 is cube free natural number. A conjugate quadratic point of $V$ is one of the form $(a + b\sqrt d, a - b\sqrt d, c)$ (note that all ...
0
votes
1answer
28 views

Find the set of primes p for which -3 is quadratic residue mod p

Find the set of primes $p$ for which $-3$ is quadratic residue $\text{mod } p$. I have started my solution like this: $1= \left(\dfrac{-3}{p}\right) = ...
3
votes
0answers
29 views

Number field attached to a finite group.

Let $G$ be a finite group. I know that the set of irreducible representations of $G$ over the complex numbers (up to isomorphism) is finite. Let us fix our attention on some irreducible ...
1
vote
2answers
55 views

About primes and Euler's totient function.

Is the number of primes $< n$ itself less than the number of positive integers that are less than $n$ and relatively prime to $n$?
0
votes
1answer
51 views

Squares in a Finite Field

Show that in any finite field,each of its elements can be written as the sum of two squares. Well,I hate to admit-this being also my first post-that I have not proven it yet.I tried to work on the ...
2
votes
1answer
21 views

Why is $\sum_{x=1}^{p-1}\left(\frac{x}{p}\right)=\left(\frac{0}{p}\right)$

For $p$ an odd prime, Why is $$\sum_{x=1}^{p-1}\left(\frac{x}{p}\right)=\left(\frac{0}{p}\right)$$ where $\left(\frac{x}{p}\right)$ is the Legendre symbol. I'm not sure if I have given enough ...