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

Rational vs irrational

If two points on a number line is shown, are rational numbers between the two points is more or irrational number is more ? I have tried using probability , my collegue who was like my teacher also ...
1
vote
1answer
47 views

Dense sequence in $[0,1]$

There is the theorem proved by Liouville which states that if $x$ is irrational then there are infinitely many fractions $\frac{p}{q}$ such that $|x-\frac{p}{q}|<\frac{1}{q^2}$, i.e. ...
0
votes
1answer
17 views

Inverse euler totient procedure

Given that if $n = p_1^{\alpha_1}\cdots p_r^{\alpha_r}$ we know that $$\phi(n) = p_1^{\alpha_1 -1}(p_1 - 1) \cdots p_r^{\alpha_r -1}(p_r-1). \quad (1)$$ So, if $\phi(n)$ was given, the method of ...
16
votes
2answers
492 views

Riemann's zeta as a continued fraction over prime numbers.

Riemann's zeta function is a function with many faces, I mean representations. I recently derived this one, bellow, as a continued fraction over prime numbers. $$ \zeta(s)=1 ...
2
votes
1answer
31 views

Finding all primes $(p,q)$ for perfect squares.

Find all prime pairs $(p,q)$ such that $2p-1, 2q-1, 2pq-1$ are all perfect squares. Source: St.Petersburg Olympiad 2011 I have only found the pair $(5,5)$ so I am thinking that maybe a modulo $5$ ...
0
votes
0answers
20 views

What are some algorithms that can be used to test if a number is transcendental or not?

Well according to the definition of transcendental numbers I find that its any number that doesn't have any polynomial equation of any degree with integer coefficients summing up to 0. So ...
0
votes
3answers
24 views

Modular Arithmetic

I am doing some exam preparation and can't figure out how to do the following question. It seems to be a regular question and was wondering if anyone who could tell me an approach to this style of ...
3
votes
0answers
60 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, en, $x^2-py^2=-1$ has no solution in integers. Thanks a lot!
0
votes
2answers
18 views

How to measure monotonicity of a list of values

I need to compare monotonicity of lists of values. I have $S=(n_1,n_2,...n_n)$, I need a function $\mathrm f(S)$ to return the monotonicity of the S. $S_1=[1,2,4,4,8]$ $S_2=[8,4,4,2,1]$ ...
3
votes
0answers
25 views

Given n , what is the sum of all gcd integers upto n with n? [duplicate]

Given an integer n, I want to find S = gcd(1,n) + gcd(2,n) + gcd(3,n) + ....gcd(n,n). Now , there are I have firgured that the number should be something like S = φ(n) + x. Now I can't draw a ...
27
votes
8answers
3k views

How can you prove that the square root of two is irrational?

I have read a few proofs that $\sqrt{2}$ is irrational. I have never, however, been able to really grasp what they were talking about. Is there a simplified proof that $\sqrt{2}$ is irrational?
7
votes
1answer
280 views

IMO 1979 problem

The question is $$\text{If }\, p, \ q\in \mathbb{N}, \;1-\frac12+\frac13-\frac14-\dotsb-\frac{1}{1318}+\frac{1}{1319}=\frac{p}{q}.\qquad \text{Prove that } 1979\mid p.$$ So my solution went like ...
0
votes
1answer
21 views

Divisiblity test for a random number n

If a number n has 60 divisors and 7n has 80 divisors, what is the greatest power of 7 that divides n. a)1 b)2 C)3 d)4
1
vote
2answers
59 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?
1
vote
0answers
52 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 ...
0
votes
1answer
19 views

Number Theory Prime Factor Problem

There is an integer N that has 12 factors, including 1 and itself, but only 3 of them are prime factors. The sum of these three prime factors is 20. What is the smallest possible value for N?
0
votes
3answers
81 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
24 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
44 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
14 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
41 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
140 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
38 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
36 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 ?
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. ...
3
votes
1answer
25 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
25 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
86 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
15 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
32 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
35 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
58 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
18 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
46 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
71 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
20 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
197 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
37 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 ...