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)

0
votes
1answer
122 views

Goldbach's Weak Conjecture

I have a few questions on GWC, as the Wikipedia's page on it appears to be somewhat incomplete. Which of the following two statements is considered as the actual GWC? Every odd number greater than ...
0
votes
3answers
178 views

At least $p^2-p$ solutions to $x^2+y^2+z^2 \equiv 1 \mod p$

I'm trying to solve a graph theory problem that relies on for any prime $p$ there being at least $p^2-p$ solutions to $x^2+y^2+z^2 \equiv 1 \mod p$. I believe its true but my number theory is rusty ...
-1
votes
1answer
95 views

Fermat Last theorem on Poly-Euler numbers

The poly-Euler numbers, denoted as $E_{n}^{(k)}$, are defined by the following generating functions :$${2\operatorname{Li}_k(1-e^{-x}) \over 1+e^{-x}}=\sum_{n=0}^\infty E_n^{(k)}{x^n\over n!}$$ The ...
3
votes
1answer
743 views

Fermat's Last Theorem where $n$ is a power of $2$

I have seen the proof that Fermat gives for $$x^4 +y^4 \neq z^2$$ which we know also works for $z^4$. BUT I am wondering if the same basic argument can be used for the power of $2^n$. Thinks 8,16,32 ...
0
votes
2answers
51 views

Proving something is primitive recursive

I'm trying to prove $f(n) = 2n$ is primitive recursive. I understand that for something to be primitive recursive it must have the following properties: $0(x)=x$ the zero function $s(x)= x+1$ the ...
1
vote
1answer
125 views

Proof of an alternative form of Fermat-Euler's theorem.

I want to know a proof of an alternative form of Fermat-Euler's theorem $$a^{\phi (n) +1} \equiv a (mod \; n)$$ when a and n are not relatively prime. I searched some number theory books and a ...
4
votes
0answers
163 views

Transfinite Knuth-arrow hierarchy vs. fast-growing hierarchy

Suppose Knuth arrow notation (and hence the hyperoperation sequence) is extended to transfinite ordinal indices as follows: Let μ be a large countable ordinal such that a fundamental sequence is ...
0
votes
0answers
224 views

Factor a big number by Pollard Rho method

How to factor $2^{2^8}+1$ by Pollard Rho algorithm? I have tried this question,but I have no clue. In order to use Pollard Rho, I should know some factor of this number right? But how can I find one?
0
votes
1answer
338 views

Binary expansion

I am trying to get my head around the left and right shift for binary expansion. The rules are: Shifting to the right ...
2
votes
1answer
55 views

When a quadratic involving three primes is a perfect square

How do we find all primes $p,q,r$ such that $p^2+q^2+rpq$ is a perfect square ? with $r=7$ and $p=q$ we have the expression a perfect square
5
votes
2answers
74 views

To solve $ \dfrac1m+\dfrac1n-\dfrac1{mn^2}=\dfrac34$

How do we find all positive integers $(m,n)$ such that $ \dfrac1m+\dfrac1n-\dfrac1{mn^2}=\dfrac34$ ?
0
votes
3answers
47 views

Number Theory help required

Hi, can someone help me solve this? $$110x \equiv 3 \pmod{73}$$ So far, I have completed the the Magic table and found the GCD. I got ...
2
votes
4answers
71 views

Fundamental Theorem of Algebra Application

Let $f(x)=a_{k}x^k+a_{k-1}x^{k-1}+a_{0}$ be a polynomial with integer coefficients and $a_{k}$ nonzero. Prove that if $a_{0}\geq2$, $f(n)$ is not prime for some integer $n$. Any ideas?
2
votes
1answer
265 views

Factors of a perfect square plus one

For large integer $a$, small integer $d$, consider the following quantity: $$a^2+d$$ What are the best lower bounds one can get for the sum $l+m$, where integers $l,m$ are such that: $$lm=a^2+d$$ ...
4
votes
1answer
229 views

Euler phi function, number theory

I am trying to find the value of $$\sum_{n=1}^{N}\sum_{d|n}d*\phi(d)$$ Is there a method to evaluate this for large N? $\phi(d)$ is the Euler phi function.
3
votes
0answers
105 views

Major arcs in the proof that every odd number is the sum of at most 5 primes

In his proof that all odd numbers greater than 1 are the sum of at most 5 primes, Terence Tao uses one large major arc around 0 rather than small ones around the rationals, which I am more accustomed ...
1
vote
1answer
62 views

Is there rational number x,y satisfy this equation?

Is there rational number x,y satisfy the equation : $$\dfrac{\sqrt{x^2+4}-x}{2}=\tanh(y)$$ Thank you
1
vote
1answer
63 views

Prove/Dis-Prove that the set of diophantine equation is infinite

Given diophantine equation $4x^3 - 3 = y^2$ ($x > 0$). How many solutions are there ? I don't know where to start, please give me a hint
1
vote
1answer
44 views

Need help in proving that $4$ divides $n$. [duplicate]

I'm pretty sure this question has a duplicate, but since I can't seem to find it, I'm asking it again. If $a_{1},a_{2}...a_{n}$ are $1$ or $-1$ and ...
6
votes
3answers
97 views

Find the value of $a^{2m}+a^m+{1\over a^m}+{1\over a^{2m}}$

Let $a$ be a complex number such that $a^2+a+{1\over a}+{1\over a^2}+1=0$ Let $m$ be a positive integer, find the value of $a^{2m}+a^m+{1\over a^m}+{1\over a^{2m}}$ My approach: I factorized ...
0
votes
2answers
48 views

$\cos(1/x)$ countable on $(0,1)$

Show that the set $S= { x \in (0,1): \cos(\frac{1}{x}) = \pm 1}$ is countable. From a practice paper. I understand that showing there is a surjection between Natural numbers and a set implies it is ...
2
votes
1answer
50 views

Find the minimum value of $S$

Let $a,b,c$ be real numbers greater than 1. Let $S=\log_a{bc}+\log_b{ac}+\log_c{ba}$ Then find the minimum value of $S$
11
votes
2answers
240 views

Infinitely many perfect squares

Are there positive integers $A,B$ such that $A2^n+B$ is a perfect square for infinitely many $n$ ? This is not my homework.
1
vote
2answers
205 views

Find all real $x$ ,such $8x^3-20$ and $2x^5-2$ is perfect square

Find all real numbers $x$,such $$8x^3-20,2x^5-2$$ is the perfect square of an integer My idea: First we find the real number $x$ such $$8x^3-20,2x^5-2$$ is postive integer numbers,and second ...
1
vote
0answers
60 views

Another triple.

Solving the equation. $X^2+Y^2+Z^2=X^3$ got some solutions, but still the question remains. Below are all the decisions or not? $X=5t^2+2t+2$ $Y=11t^3+5t^2+2t$ $Z=2t^3+10t^2+4t+2$ And more. ...
2
votes
0answers
54 views

How to prove that every $l$ (such that $ 2 \leq l \leq \lfloor \sqrt{k^2+2n+1} \rfloor $) divides at least one of the following numbers?

$ k^2+2n, k^2, k^2+1, 2n, 2n+1$, (for some $n$) if $k$ is even and $0 < n < k$. I have no idea of how to prove that. I'm working on Legendre's conjecture. Update 1: Yes, for $n=0$ all $l$ ...
2
votes
1answer
48 views

$2^n+1 =xy \implies (2^a|(x-1) \iff 2^a|(y-1))$

I'd like my proof to be verified of the following exercise from Niven's The Theory of Numbers. Section 1.1 Problem 52: Suppose $2^n+1=xy$, where $x$ and $y$ are integers $>1$ and $n>0$. Show ...
2
votes
2answers
94 views

$ ab-1|a^2+ab+b^2 $

I hava a number theory problem. I think on it yestarday night and today, afternoon. The problem : $ a,b $ are two natural numbers such that : $ ab>1 $ how many pairs $ (a,b) $ is there such that ...
2
votes
2answers
49 views

To prove $m$ is not a square of a natural number

Let $m$ be a natural number with digits consisting if only $6$'s and $0$'s p. Prove that $m$ is not the square of a natural number.
2
votes
1answer
31 views

How can I conclude that the integers $a r_1, a r_2 … ar_{\phi(m)}$ modulo $m$ are a permutation of the integers $r_1,r_2,…,r_{\phi(m)}$?

How can I conclude that the integers $a r_1, a r_2 ... ar_{\phi(m)}$ modulo $m$ are a permutation of the integers $r_1,r_2,...,r_{\phi(m)}$ given the proofs that $(ar_i,m) = 1$ ($\gcd$) for every $i$ ...
1
vote
0answers
29 views

Using $ \gcd(a,b) = \gcd(b,r) $ if $ a \equiv r \pmod b$ for GCD?

It should be true that $\gcd(a,b) = \gcd(b,r) $ if $ a \equiv r \pmod b$. But: How can I use this equality to compute the GCD of $a$ and $b$? It seems as if $r$ is of the form $r = k\cdot b + s$ ...
0
votes
0answers
30 views

Number theory proof difference and product proof

Let $ a, b, c, d$ be four arbitrary integers. Prove that the product of the six differences $$b-a, c-a, d-a, c-b, d-b, d-c $$ is divisible by 12. I tried multiplying the whole thing out, which was ...
1
vote
3answers
154 views

if $ a_{n+1}=n^2+3\sqrt{\frac{3a_{n}-a_{n-1}}{2}}$ this sequence have infinite number of “good” term

Question: Given a sequence $\{a_{n}\}$, call a term $a_{k}$ "good", if there exist $a_{m},a_{n}$, such that $$a_{k}=a_{m}a_{n}$$($a_{m}$ and $a_{n}$ are allowed to be equal.) Otherwise it is ...
1
vote
0answers
61 views

Proof: There are infinite prime numbers of the form 4k+3 [duplicate]

I have to proof if true or wrong: There are infinite prime numbers of the form 4k+3. I want to proof: Yes, this is true. My ideas: 1) Assume - as a contradiction - that there are only infinite prime ...
1
vote
1answer
67 views

$(2,1+\sqrt{-5})$ has integral basis $2$, $1+\sqrt{-5}$

$2,1+\sqrt{-5}$ is an integral basis for the ideal generated by them in $\mathbb{Z}[\sqrt{-5}]$. Is there a quick way to see this? What if these two are replaced with another pair? My method: Write ...
-3
votes
3answers
261 views

Congruence $x^n\equiv2 \pmod{13}$ (Multiple Choice)

I was trying to solve the following problem.Please help. Consider the $x^n\equiv2 \pmod{13}$. It has a solution for $x$ if $n=5$ $n=6$ $n=7$ $n=8$ It may have more than one correct options. Thnx ...
0
votes
0answers
23 views

Prove that for every prime $p$ we have $x = g^i \; \text{mod} \; p$

While reading some lecture notes, I saw the following result stated as a fact, however I am not sure how to prove it: For every prime $p$, there exists a number $g$ such that for every number $x$ ...
1
vote
2answers
41 views

Congruences - Evaluate $5^{17} \equiv b \pmod {70}$

I'm currently studying for my summer maths exam and I've come across a problem that has appeared in some form in all of the previous years' papers. Unfortunately, our Maths teacher wasn't very good ...
2
votes
0answers
77 views

How to prove sum of two numbers of the two following forms can be equals to sum of two numbers not of the forms?

The two forms are: $\ 3x^2 + (6y-3)x - y\ $ $\ 3x^2 + (6y-3)x + y - 1, \ \ x,y \in \mathbb{Z}^{+}$ For example: $\ \ \ 5 = \ 3*1^2 + (6*1-3)*1 - 1\ $ ,when $\ x = y = 1\ $,of the two forms $\ ...
1
vote
1answer
35 views

Divisor function of factorials and other integers

Is there a proof or any known value of $x$, for which $x<n!$ and $\sigma(n!)<\sigma(x)$
4
votes
3answers
60 views

$l^2+m^2=n^2$ $\implies$ $lm$ is always a multiple of 3 when $l,m,n,$ are positive integers.

Let $l,m,n$ be any three positive integers such that $l^2+m^2=n^2$ Then prove that $lm$ is always a multiple of 3.
2
votes
1answer
87 views

Integrality Conjectures

Here are some interesting conjectures I would like to prove. For all positive integers $a=bc,m,n$ the following expressions are integers: $$c\sum_{k=1}^{am}k\left\{\frac{kbn}{am}\right\}$$ ...
3
votes
2answers
150 views

Dedekind Sum Integrality Result

Can we prove the following is always an integer? $$6b\sum_{k=1}^bk\left\{\frac{ka}{b}\right\}$$ where $\{x\}=x-\lfloor x\rfloor$ denotes the fractional part operator. UPDATE: Through the ...
2
votes
1answer
228 views

ramification in a cyclic extension of a cyclotomic field

Let $F$ be a cyclotomic field generated by a primitive $p$-th root $\zeta$ of 1. Is it known that the prime ideal $(1-\zeta)$ in $\mathcal{O}_F$ ramifies in the extension $F(q^{\frac{1}{p}})$ where ...
1
vote
1answer
114 views

Bound of a certain sum of cosines

Let $N$ be a sufficiently large natural number and let $k \in \mathbb{N}$ such that $k | N$. Suppose I have a sequence $\{ \alpha_j \}_{j=1}^N \subseteq [0,1)$, which satisfies $$ \# \{ j \in \{1, ...
5
votes
1answer
92 views

Non-unique prime factorisation

G is a number system where $(a,b)$ belongs in G where $a$ and $b$ is an element of the integers $\mathbb{Z}$. multiplication is defined as follows: $(a, b) \times (c, d) := (ac-5bd , ad+bc)$ ...
2
votes
1answer
73 views

How prove this $ n = \frac {a^3 + 2b^3} {c^3 + 2d^3}. $ infinitely many special numbers

Qustion A special number is a positive integer $n$ for which there exists positive integers $a$, $b$, $c$, and $d$ with $$ n = \dfrac {a^3 + 2b^3} {c^3 + 2d^3}. $$ Prove that i) there are ...
3
votes
1answer
85 views

$p$ is an odd prime number where $p=3k+1\Longleftrightarrow\exists a,b\in\Bbb Z^+$ such that $p=a^2+ab+b^2$

Let $p$ be odd prime number,show that: $$p=3k+1\Longleftrightarrow \exists a,b\in\Bbb Z^+ \textrm{ such that } p=a^2+ab+b^2$$ I guess this is true because I find when: $p=7,k=2$,and $$7=2^2+2\cdot ...
2
votes
1answer
57 views

how to calculate all numbers of the form $6x-1, 6x+1, 6x+5$ that are not divisible by $5,7$ or $11$?

This is purely a hobbist question, I would simply like to know what methods are currently used to find the answer to this question. (Does modular arithmetic suffice in finding all the "$x$" values ...
0
votes
1answer
99 views

Pythagorean quadruple generators with a gcd relation

For non-negative integers $m,n,q,p$ with $\gcd(m,n,q,p)=1$, assume we have: $$\gcd(mq+np,b)=|nq-mp|$$ for some integer $$b<mq+np$$ and that $$8\nmid\,mq+np,$$ $$m+n+p+q\equiv 1\mod 2.$$ Can ...