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
2answers
433 views

When does -1 have a squareroot in a finite field? (-1 as a quadratic residue)

For example in $\mathbb{F}_5$, $2^2=3^2=-1$. However, in $\mathbb{F}_3$, there is no solution to $x^2=-1$. When do the squareroot(s) exist, and if they do, can we say anything about their ...
0
votes
0answers
78 views

Let f(x,y) be a positive semidefinite quadratic form with discriminant 0. Show that f is equivalent to the form h(x,y) = $gx^{^{2}}$.

Let f(x,y) = $ax^{^{2}} + bxy + cy^{^{2}}$ be a positive semidefinite quadratic form of discriminant 0. Put g = gcd(a,b,c). Show that f is equivalent to the form h(x,y) = $gx^{^{2}}$. I know that if ...
1
vote
0answers
36 views

Question about finite sums and integer recursions.

Let $n$ be a positive integer and let $g(n)$ be a given strictly increasing integer function such that $0<g(n)<n$ for all $n$. Also the sequence $ |g(n) - n|$ is unbounded as $n$ grows. Let $f(...
6
votes
5answers
296 views

What is the proof to the fact that all prime numbers are 1 above or below a 6 multiple? [duplicate]

I was just having an argument with my friend and I dunno how we got here. But he suddenly said all primes are 1 above or below a multiple of 6. At first I tried a lot of primes but couldn't disprove ...
3
votes
2answers
159 views

Does it hold that the $p$-adic completion of the integers equals the completion of the localization in $p$?

maybe this is a stupid question, but I could not solve it even for the ordinary integers $\mathbb{Z}$. Furthermore, I don't have to much knowledge on algebraic number theory and ramifications. Let $K$...
4
votes
3answers
197 views

$x^2+1$ is almost always square free

It seems like $x^2+1$ is almost always square free. Any research or heuristics why? I tried breaking the problem into solving $$x^2-ky^2=1$$ For various $k$, and I conjecture that for every $k$ there ...
3
votes
1answer
90 views

Basic Iwasawa Theory Question

I'm looking at a paper that introduces some terms and intends to use concepts from Iwasawa Theory. I instantly find myself stuck at the second sentence and even after much searching on the internet, I ...
1
vote
3answers
98 views

Use the binomial theorem to give a formula for positive integers $x_{k}$ and $y_{k}$ such that $(3 + 2\sqrt{2})^{^{x}} = x_{k} + y_{k}\sqrt{2}$.

Use the binomial theorem to give a formula for positive integers $x_{k}$ and $y_{k}$ such that $$(3 + 2\sqrt{2})^{^{x}} = x_{k} + y_{k}\sqrt{2}.$$ Is this simply just applying the binomial ...
0
votes
0answers
55 views

Iterative function eventually reaching identity

For integers $a,b$ we define $f((a,b))=(2a,b-a)$ if $a<b$ and $f((a,b))=(a-b,2b)$ if $a\geq b$. Given a natural number $n>1$ show that there exist natural numbers $m,k$ with $m<n$ such that $...
2
votes
1answer
92 views

Sums involving square of Moebius function

I try to estimate the following sum: $$ \sum_{n \leq x}\mu(n)^2 f(n) $$ where $\mu(n)$ is a Moebius function and $f(n)$ is some multiplicative arithmetic function. If I understand it correctly it is ...
1
vote
2answers
81 views

Proving that any common multiplication of two numbers is a multiplication of their least common multiplication

Im trying to prove that if there are to numbers $n,m$ (natural numbers), and their smallest common multipe is $k$, so that $k = n·i$ and $k = m·j$ for some $i,j$ natural numbers, any common multiple $...
0
votes
0answers
349 views

Proof of convergence of Kaprekar's Constant

I've tried googling this one a bit but nothing seems to come up, even though its considered to be a well known fact. Why does the kaprekar process of taking a 4 digit number: L, generating L' and L'' ...
0
votes
2answers
73 views

product of comprime numbers and UFD

It is well-known that if a product of coprime numbers is a perfect square, so are the numbers. The proof depends on fundamental theorem of arithmetic, and this implies that in a UFD, if ab is a ...
2
votes
2answers
122 views

Flip cards to get maximum sum

Given N cards where if ith card has number x on its front side then it will have -x on back side and a single operation that can be done only once that is to flip any number of cards in consecutive ...
1
vote
1answer
57 views

Find extra work done by Bob

Alice has challenegd Bob game of N puzzle.N puzzle is played on N*N grid with each cell containing distinct numbered tile from 1 to N*N-1 Except one which is empty cell and represented as 0. Move ...
0
votes
0answers
65 views

variation of the Euler $\phi$ function?

Let $n \leq m$ be positive integers. Is there a function or expression giving the cardinality of the set $\{r \in \mathbb{Z}^+| 1 \leq r \leq m, \gcd(r,n) = 1 \}$? If $n = m$, it's just $\phi(n)$.
2
votes
3answers
49 views

If algebraic $a$ has degree $n$, so does $-a$

I feel like the best way to move forward is to use a contradiction proof. Since $a$ is algebraic, and is of degree $n$, it has a minimal polynomial of degree $n$, so we can write $$f(a)=\sum_{k=0}^n{...
0
votes
2answers
101 views

how to find taxicab numbers but for squares?

Natural numbers that can be written as the sum of squares in two or more ways. The first ten numbers are 50, 65, 85, 125, 130, 145, 170, 185, 200, 205. $$ n = a^2 + b^2 = c^2 + d^2\\ a^2 − c^2 = d^2 −...
6
votes
2answers
102 views

minimal polynomial given an algebraic number

I am trying to find the minimal polynomial for the algebraic number $1+\sqrt{2}+\sqrt{3}$. My original thought was just let $\alpha=1+\sqrt{2}+\sqrt{3}$. The method I use though seems very ...
6
votes
1answer
145 views

Can the product of $n$ factorials be $n$ factorial?

Are there any solutions to the equation $a_1!\cdot a_2!\cdots a_n!=n!$ with all variables being integers greater than or equal to $2$?
4
votes
1answer
125 views

Class group of $\mathbb{Q}(\sqrt[4]{-2})$

I would like to show directly that $C(K)$ is trivial, where $K = \mathbb{Q}(\sqrt[4]{-2})$. Write $\delta = \sqrt[4]{-2}$. It is pretty easy to see that $\mathcal{O}_K = \mathbb{Z}[\delta] = R$. Then $...
4
votes
1answer
131 views

Permutation Partition Counting

Consider the number $n!$ for some integer $n$ In how many ways can $n!$ be expressed as $$a_1!a_2!\cdots a_n!$$ for a string of smaller integers $a_1 \cdots a_n$ Let us declare this function as $\...
2
votes
0answers
114 views

“Remainder” operation in mod 2^32

I debated posting this here, in the cryptography SE, or the programming SE. Obviously, I chose here, but I'm not confident in my choice... I'm attempting to "undo" a function, but I've hit a slight ...
4
votes
2answers
131 views

Difficult generating function

Define a beautiful number to be an integer of the form $a^n$, where $a\in\{3,4,5,6\}$ and $n$ is a positive integer. Prove that each integer greater than $2$ can be expressed as the sum of pairwise ...
3
votes
2answers
311 views

explicit example of computing ray class field for imaginary quadratic?

Given an imaginary quadratic number field K, we can get its ray class field mod some ideal $\mathcal{m}$ by adjoining the j-invariant of an elliptic curve with complex multiplication given by $\...
3
votes
1answer
141 views

Last 7 digits of 7th powers

Alice and Bob play the following game. They alternately select distinct nonzero digits from $1$ to $9$, until they have chosen seven such digits. Consider the resulting seven-digit number by joining ...
5
votes
1answer
114 views
1
vote
1answer
75 views

How to have this equation $s^2-2(p+q+r+2pqr)s+(p^2+q^2+r^2-2(pq+qr+rp)-4)=0$?

Old Question: For $x,y,z\in N^{+}$, if such $(xy+1)(yz+1)(zx+1)$ is a perfect square ,show that $$(xy+1),(yz+1),(xz+1)$$ are all perfect square . and I konw this PDF have solution, http://math....
4
votes
2answers
71 views

Proving Fibonacci inequality

I didn't see a question regarding this particular inequality, but I think that I have shown by induction that, for $n>1$. I am hoping someone can verify this proof. $$\left(\frac{1+\sqrt{5}}{2}\...
0
votes
0answers
44 views

general local to global principle

Consider the Diophantine equation $f(x)=0$, where x is a vector of integers and $f: \mathbb Z^n \rightarrow \mathbb Z$ is a polynomial function. Is the following statement true? The structure of the ...
4
votes
2answers
415 views

Solutions to the Mordell Equation modulo $p$

It is well known that for any nonzero integer $k$ the Mordell Equation $x^2 = y^3 + k$ has finitely many solutions $x$ and $y$ in $\mathbf Z$, but it has solutions modulo $n$ for all $n$. One proof of ...
0
votes
1answer
41 views

Find the number of positive integer $a \leq n$ such that $(a,n) = (a+1,n) = 1)

For every positive integer $n$, let $$A_n = \{a \in \mathbb{N} \mid 1 \leq a \leq n \mid gcd(a,n) = gcd(a+1, n) = 1\}$$ Evaluate $\mid A_n\mid$ Assume that $n$ has the factorization $n=p_1^{a_1}p_2^{...
2
votes
2answers
209 views

How prove this $3^{\frac{5^{2^n}-1}{2^{n+2}}}\equiv (-5)^{\frac{3^{2^n}-1}{2^{n+2}}}\pmod {2^{n+4}}$

Question: show that: $$3^{\frac{5^{2^n}-1}{2^{n+2}}}\equiv (-5)^{\frac{3^{2^n}-1}{2^{n+2}}}\pmod {2^{n+4}},n\geq 1$$ My idea: since I have prove $$5^{2^n}-1\equiv 0\pmod {2^{n+2}}$$ $$3^...
1
vote
2answers
60 views

Help with proof regarding degrees of polynomials

How do you prove that if $f(x)\mid g(x)$ in $F[x]$, then either $g(x) = 0$ or $\deg(g(x)) \geq \deg(f(x))$ I'm not really sure how to prove these types of statements
1
vote
1answer
81 views

Möbius function verification

I am looking to verify my answer to the question $$F(n)=\sum_{d|n}{\mu(d)\sigma(d)}=(-1)^{\omega(n)}\prod_{j=1}^{\omega(n)}{p_j}$$ Where $\mu$ is the Möbius function, $\sigma$ is the sum of divisors ...
1
vote
2answers
54 views

Diophantine solution to a fraction

How can we find solutions to the following equation: $$ y=\dfrac{x^2-1085}{14718-2x}$$ where $x,\ y$ are integers.
1
vote
1answer
85 views

Sizes of Blocks of Consecutive Integers Divisible by at Least One Prime Less than or Equal to $r$.

Let $f(r)$ be the largest integer such that there exists a block of $f(r)$ consecutive integers each divisible by some prime that is less than or equal to $r$. For example, $f(2)=1$ because it is ...
1
vote
1answer
69 views

regarding pseudo-prime numbers.

If $W$ is an odd composite number and $-1+2^{W-1}$ is divisible by $W$ yet not by $W^2$, then $W^2$ does not divide $-1+ 2^{W(W-1)}$. Is this true? (forgive my use of symbols,I have no good math ...
2
votes
4answers
229 views

What is the remainder when the below number is divided by $100$?

What is the remainder when the below number is divided by $100$? $$ 1^{1} + 111^{111}+11111^{11111}+1111111^{1111111}+111111111^{111111111}\\+5^{1}+555^{111}+55555^{11111}+5555555^{1111111}+55555555^{...
2
votes
2answers
396 views

Fibonacci number ending with given sequence of digits

Related to this question: For any given sequence of digits, does a Fibonacci number exist ending with such sequence? If not, it would be nice to find the smallest counterexample. (in other words,...
2
votes
0answers
48 views

Polynomial Density Theorem

So I was consider Lagrange's 4-square theorem and came up with this generalization: Given a polynomial with rational coefficients $$P(x) = a_0 + a_1x + ... + a_nx^n$$ Determine if there exists ...
0
votes
2answers
281 views

Finding all possible pairs of integers $(a,b)$ such that $a^b=n$.

Given a large integer $n$ (could be as large as $10^{18}$), how can I find all possible pairs of integers $(a,b)$ such that $$a^b=n.$$ A fast algorithm is preferable. The question How to quickly ...
1
vote
0answers
99 views

How do ramanujan sums and the sum of 2 squares relate?

I read on the Wikipedia page for the ramanujan sum a formula for the sum of 2 squares in terms of the ramanujan sums. But I did not get it. http://en.wikipedia.org/wiki/Ramanujan_sum How do ...
1
vote
1answer
63 views

Contracted ideals in number fields

I am trying to translate a section of Wolfgang Krull's report "Idealtheorie". At one point (Section $7$ on Quotient Rings) I believe that he makes something like the following statement: Suppose for ...
2
votes
0answers
131 views

Fermat pseudoprimes p to base 2 (AKA Sarrus or Poulet numbers) with special properties

Are there any known Fermat pseudoprimes $p\;$ to base $2\;$ (Sarrus or Poulet numbers) with the properties $q = (p-1)/2\;$ is prime and $p \equiv 0 \pmod 3?$ I was not able to find any example up to $...
1
vote
1answer
41 views

How find the minimum of the value $n$ such$105\mid \left(9^{p^2}-29^p+n\right)$

Find the minimum of the value $n$,such for any prime number $p>3$,have $$105\mid\left(9^{p^2}-29^p+n\right)$$ My since $$105=5\times 3\times 7$$ so $$9^{p^2}-29^p+n=(10-1)^{p^2}-(30-1)^{p}+n)\...
3
votes
0answers
101 views

An Inequality with Prime Numbers

Let $m\geq 8$ be an integer, and let $q$ be the smallest prime that is greater than $m$. Let $p$ be a prime that satisfies $q\leq p<q^2$, and let $p_0$ be the smallest prime such that $p_0q>p^2$....
1
vote
0answers
68 views

Finding the number of elements in $\left(ℤ[i]\right)_m$

If $m$ = $m_1$ + $m_1i$ ∈ $ℤ[i]$, is there a general formula to find the number of elements in $\left(ℤ[i]\right)_m$?
1
vote
3answers
258 views

Is there a polynomial equation for $f(n) = n!$ and if so what is it?

And I am not necessarily talking about $f(n) = n(n-1)(n-2)...(3)(2)(1)$ in its factored form; Well it could be that but then I would like a general way of expansion. Thanks in advance!
13
votes
2answers
3k views

Proof that $26$ is the one and only number between square and cube

$x^2 + 1 = z = y^3 - 1$ Why $z = 26 $ and only $26$ ? Is there an elementary proof of that ?