Questions on more advanced topics of number theory. 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
23 views

How find this $5xy\sqrt{(x^2+y^2)^3}$ can write the sum of Four 5-th powers of positive integers.

Find all positive integer $x,y$ such $$5xy\sqrt{(x^2+y^2)^3}$$ can write the sum of Four 5-th powers of positive integers.In other words: there exst $a,b,c,d\in N^{+}$ such ...
1
vote
3answers
49 views

Last Two Digits Problem

I'm trying to find the last two digits of ${2012}^{2012}$. I know you can use (mod 100) to find them, but I'm not quite sure how to apply this. Can someone please explain it?
0
votes
4answers
77 views

Testing If a Three/Four Digit Number is Prime or Not

Thank you for providing such great help. Thanks to math.stack site. I would like to know a good method to test any three/four digit number prime or not? I don't want to go any C or Java or any ...
0
votes
0answers
18 views

Legendre's Conjecture

I have read and heard conflicting reports about whether or not Legendre's conjecture has been proven. Refresh: Legendre believed that there will always be at least one prime between (n)^2 and (n+1)^2. ...
2
votes
4answers
43 views

Count the divisors of n with particular property

Take $n = \prod_{i=1}^r {p_i}^{\alpha_i}$, where each $p_i$ is a prime and $\alpha_i\geq 1$. How many divisors of $n$, not equal to $n$, contain at least one $p_i$ with the corresponding multiplicity ...
0
votes
1answer
12 views

Question regarding solving a modulo equality

Two Equations: ab % c = d (ci + d) % c = d, i $\in \mathbb N$ I want to solve for b given the above two equations with a, c, and d known. ab = ci + d b = (ci + d) / a i = (k + an), n $\in ...
0
votes
2answers
36 views

If $\gcd(a, b) = 1$ then prove that $\gcd(a+b, a^2-ab+b^2) = 1$ or $3$?

If $\gcd(a, b) = 1$ then prove that $\gcd(a+b, a^2-ab+b^2) = 1$ or $3$? I am shamelessly asking how to solve the problem? I have no idea how to start and solve. Please help.
8
votes
2answers
136 views

Given the factors of $N$, is there a method for computing the factors of $N-1$ or $N+1$?

Given the prime factorization of $N$, is there a known method for computing the prime factorization of $N-1$ or $N+1$, which is more efficient than the best known method for doing that without it? I ...
1
vote
2answers
34 views

Proof about Number Fields

It is a known result that if $\alpha$ is an algebraic integer in a number field $K$, i.e. $\alpha \in \mathcal{O}_K$, then its trace and norm are integers. I am looking over a proof of this, which ...
2
votes
1answer
33 views

How to know if the mth root of n is an integer?

If n can be represented in binary as a x bit integer, is there any algorithm such that we can determine if the mth root of n is an integer in time polynomial of x ?
3
votes
0answers
50 views

diophantine equation $ |x^2-py^2|=\frac{p-1}{2} $

Prime $p\equiv3\pmod4$, then the equation $$ |x^2-py^2|=\frac{p-1}{2} $$ has a solution in integers obviuosly, $x^2-py^2=-1$ has no solution in integers. How about this problem? Thanks a lot!
2
votes
1answer
52 views

How to find $\sum_{d\mid n}(w(d)w(\frac{n}{d}))$?

i) $w(n)$ is the prime divisor count function. For example $w(6)=2$ ii) Let prime factorization of $n=p_{1}^{a_{1}}p_{2}^{a_{2}}.....p_{w(n)}^{a_{w(n)}}$ iii) Lets define this function. ...
2
votes
1answer
24 views

How prove this $\sum_{t|n}(d(t))^3=\left(\sum_{t|n}d(t)\right)^2$

show that $$\sum_{t|n}(d(t))^3=\left(\sum_{t|n}d(t)\right)^2$$ where $d(n)$ is the number of positive divisors of $n$. see this have simaler $$1^3+2^3+\cdots+n^3=\left(1+2+\cdots+n\right)^2$$ maybe ...
3
votes
2answers
23 views

How prove or disprove $\gcd(lcm[a_{1},a_{2},\cdots,a_{n}],a_{n+1})=\cdots$

let $a_{i},i=1,2,\cdots,n,n+1$ be positive integer numbers,prove or disprove $$\gcd([a_{1},a_{2},\cdots,a_{n}],a_{n+1})=[\gcd(a_{1},a_{n+1}),\gcd(a_{2},a_{n+1}),\cdots,\gcd(a_{n},a_{n+1})]$$ ...
1
vote
4answers
84 views

If $d=\gcd(a+b,a^2+b^2)$, with $\gcd(a,b)=1$, then $d=1$ or $2$

Suppose $\gcd(a,b)=1$. Let $d=\gcd(a+b,a^2+b^2)$. I want to prove that $d$ equals $1$ or $2$. I get that $d\mid2ab$ but I can't find a linear combination that will give me some help to use the fact ...
0
votes
2answers
13 views

On extracting primes from coprimes

Proof or disprove the following statement - There exists infinitely many $a$ and $b$ which are pair of co-prime integers , either $ab+1$ or $ab-1$ is prime. Motivation- Looking at some twin prime ...
0
votes
1answer
22 views

System of Diophantine equations.

Quite interesting are there any ideas on solving systems of equations like these? $\left\{\begin{aligned}&a^2+b^2=c^2\\&(a+k)^2+(b+k)^2=q^2\end{aligned}\right.$ Although I recorded such ...
1
vote
1answer
52 views

Scheme over a DVR

Let $\mathcal{O}$ be a discrete valuation ring with finite residue field $k$ of characteristic $p$. Let $S=\mathrm{Spec}(R)$ be a noetherian scheme over $\mathrm{Spec}(\mathcal{O})$. Are there ...
0
votes
3answers
30 views

Number Theory Remainder Question

I'm trying to find the answer to the following: What is the remainder when 9^2012 is divided by 11? Apparently, you're supposed to use Fermat's Little Theorem, but I'm not sure how to use it to solve ...
0
votes
1answer
19 views

Equation with a sum for the prime-counting function involving the Mobius function

I have come across the statement that $$ \sum_{n\leq x}\sum_{d\mid(n,P_z)}\mu(d) = \sum_{d\mid P_z}\mu(d) \left[\frac{x}{d}\right], $$ where $P_z=\prod_{p\leq z}p$ where $p$ is prime, $\mu(d)$ is the ...
4
votes
0answers
33 views

Applications of generating functions to number theory

I am familiar (at least at a cursory level) with the extensive role generating functions play in the theory of partitions. What are some other prominent applications of generating functions to number ...
0
votes
2answers
57 views

Find three numbers given their sum, product and sum of their squares

Given three unknown positive integers. Is it possible to find the three numbers if we are given their Sum->(a+b+c) = X Product-> (abc) = Y Sum of Squares-> (a^2 + b^2 + c^2) = Z
0
votes
0answers
17 views

Find the highest LCM for n numbers in a range

I'm designing a component that takes a clock in (i.e. a periodic signal), and outputs a periodic signal with a lower frequency. To do so, I use two counters of different sizes. Here's an example, with ...
0
votes
1answer
32 views

Sum of Euler Phi equalities

Show: $\sum_{n\le x} \phi(n) [\frac{x}{n}] = \sum_{n \le x} \sum_{m\le \frac{x}{n}} \phi(m)$ I know the left most sum boils down to $\sum_{n\le x} n$. If we know that $m|\frac{x}{n}$ then we know ...
7
votes
1answer
149 views

Intuitively, why is the Euler-Mascheroni constant near sqrt(1/3)?

Questions that ask for "intuitive" reasons are admittedly subjective, but I suspect some people will find this interesting. Some time ago, I was struck by the coincidence that the Euler-Mascheroni ...
1
vote
1answer
45 views

Solve a system of diophantine equations

I have a problem with elemental number theory. I started with the expression $$ (a - \frac{1}{b})(b - \frac{1}{c})(c - \frac{1}{a}) $$ and task to find all natural $a,b,c$ so that the result of the ...
4
votes
1answer
68 views

How prove this $a^n-b^n$ always have prime factor $P$ and $P>n$

Let $p_{1},p_{2},p_{3}$ be different prime numbers, and let the positive integer $n$, be defined by $$n=p_{1}p_{2}p_{3}.$$ Show that: For any two positive integer $a,b$ ,then $a^n-b^n$ ...
2
votes
0answers
18 views

Recovering congruence conditions from the Hilbert class polynomial for idoneal numbers

Before I can ask my question, I need to introduce some terminology and background. Statement 1: Let $n$ be one of Euler's 65 convenient numbers. Then we can find congruence conditions such that ...
6
votes
4answers
196 views

What's the value of $n+\cfrac{n}{n+\cfrac{n}{n+\cfrac{n}{\vdots}}}$ for $n\in\mathbb{C}$?

Write $$\phi_n\stackrel{(1)}{=}n+\cfrac{n}{n+\cfrac{n}{n+\cfrac{n}{n+\cfrac{n}{\vdots}}}}$$ so that $\phi_n=n+\frac{n}{\phi_n}$, which gives $\phi_n=\frac{n\pm\sqrt{n^2+4n}}{2}$. We know ...
0
votes
2answers
27 views

Sum of square representations

How can I find the number of proper representations of a number n as a sum of 2 squares where $n \le 10000$ ? How to calculate such a thing?
1
vote
3answers
97 views

how do i prove that $17^n-12^n-24^n+19^n \equiv 0 \pmod{35}$

How do i prove that $17^n−12^n−24^n+19^n≡0(\mod35)$ for every possitive integer n. Can anyone give me a hint of how to start?
3
votes
0answers
37 views

Formula to round up to the next multiple not divisible by $2$ or $3$?

I want a formula that rounds up any integer to the next multiple of a given prime, which is not divisible by $2$ or $3$, so it is either $p$ or $5p \pmod{6p}$. The simplest formula is preferred. I've ...
1
vote
8answers
110 views

Calculate the last digit of $3^{347}$

I think i know how to solve it but is that the best way? Is there a better way (using number theory). What i do is: knowing that 1st power last digit: 3 2nd power last digit: 9 3rd power last digit: ...
11
votes
4answers
1k views

Detecting perfect squares faster than by extracting square root

Given the radix-$r$ representation of a integer $n$, and a small integer constant $k$, there is an $O(\log n)$ algorithm for detecting whether $n$ is a multiple of $k$, namely, division, which ...
0
votes
0answers
36 views

Matrices and number theory

If $a$ and $b$ are positive integers, and $g$ and $h$ are respectively their gcd and lcm, we need to show that $ \begin{pmatrix} a & 0 \\ 0 & b \end{pmatrix} \sim \begin{pmatrix} g ...
0
votes
0answers
6 views

What is the basis for why the linear congruential generator works as a good hash function?

The linear congruential generator (LCG) is often taught in introductory computer science classes as a good hash function. What is some mathematical justification for why the LCG works and why it works ...
4
votes
1answer
99 views

Primality of the number of obtained by concatenating the n consecutive digits

Let $f_n$ be the number obtained by concatenating the first $n$ numbers (in base 10). For example $f_1 = 1, f_3 = 123$ and $f_{13} = 12345678910111213.$ Now if $n$ is even or divisible by $5$ then ...
0
votes
0answers
10 views

Help with proving using diophantine eqn

I need to show that if D is a diagonal matrix with integral elements then there is a diagonal matrix S in Smith normal form such that D~S. Deduce that every mxn matrix A with integral elements is ...
78
votes
0answers
2k views

All polynomials with no natural roots and integer coefficients such that $\phi(n)|\phi(P(n))$

Let $P(x)$ be a polynomial with integer coefficients such that the equation $P(x)=0$ has no positive integer solutions. Find all polynomials $P(x)$ such that for all positive integers $n$ we have ...
1
vote
1answer
43 views

How to convert a integral into the another?

There is a function here: http://functions.wolfram.com/NumberTheoryFunctions/PrimePi/21/01/01/0001/ How to convert it into the answer for indefinite integral $\int \pi(x) dx$ where pi(x) stand for ...
10
votes
2answers
196 views

Very curious sequence of integrals $I_n=\int_0^1 \frac {(x(1-x))^{4n}} {1+x^2}\mathrm dx$

I was studying the behaviour of very curious sequence of integrals $$I_n=\int_0^1 \frac {(x(1-x))^{4n}} {1+x^2} \,\mathrm dx$$ which gives a very beautiful result for $n=1$; I tried to calculate for ...
5
votes
1answer
57 views

Problems that are made easy by using p-adic numbers

Does anybody know of elementary problems that can be be solved using the p-adics? Solutions are preferred.
0
votes
0answers
18 views

How to apply the generalised divisibility rule to numbers of the form $10^k+n$

This is kind of a long question but bear with me. There's actually a question mark at the end. I'm trying to apply the generalised (decimal) divisibility rules to numbers of the form $10^k+n$ where ...
1
vote
0answers
16 views

Show that the solutions lifted by Hensel's lemma, are the only solutions in $\mathbb{Z} / p^k \mathbb{Z}$

Suppose that $f(x) \in \mathbb{Z}[X]$ is a polynomial to which we can apply Hensel's Lemma. Suppose the set $A$ is the set of solutions of $f(x)$ in $\mathbb{Z} / p \mathbb{Z}$. I'd like to show that ...
0
votes
3answers
34 views

Triangular numbers for numbers.

Interestingly for triangular numbers: $X(X+1)+Y(Y+1)=Z(Z+1)+a$ $a$ - this number is determined by the condition of the problem. Are all numbers equation has a solution? And what kind of formula in ...
0
votes
3answers
33 views

Every integer greater than 1 is divisible by at least one prime. Can anyone please express this in logical notation

Every integer greater than 1 is divisible by at least one prime. Can anyone please express this in logical notation
0
votes
0answers
17 views

Stuck in quadratic forms and discriminats problem

So I'm stuck in a pretty easy question about discriminants and quadratic forms of equations. I have already proved one side of the problem: we suppose that $x_0, y_0$ are the solutions to the ...
3
votes
2answers
43 views

integral roots for $f(x) = 41$ if $f(x) = 37$ has 5 distinct integral roots.

Given a polynomial $f(x)$ with integral coefficients and $f(x) = 37$ has 5 distinct integral roots, find the number of integral roots of $f(x) = 41$? My Approach: Say $f(x) = ...
0
votes
2answers
16 views
4
votes
3answers
84 views

How find this $x^3-5x+10=2^y$

let $x,y$ is positive integer,and such $$x^3-5x+10=2^y$$ find all $x,y$. since $$x=1\Longrightarrow 1^3-5+10=6$$ can't $$x=2,2^3-5\cdot 2+10=8=2^3$$ so $x=2,y=3$ $$x=3,LHS=27-15+10=22$$ ...