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)

5
votes
1answer
24 views

Congruences and prime powers

I have just a small question that probably is not hard to answer, but I could not find and elegant solution to this question. Let $p$ and $q$ be prime numbers. $$5^q\equiv 2^q \pmod p$$ $$5^p\equiv ...
3
votes
1answer
30 views

If $d|n$, then $\phi(d)|\phi(n)$

Where $\phi(n)$ denotes Euler's Totient Function. My proof follows, I was hoping someone could verify it, and give critique. Let $d,n\in\mathbb{Z}^+$ so that $d|n$. By the Fundamental Theorem of ...
0
votes
0answers
5 views

Question regarding the sum of the reciprocal of the values in Sylvester's sequence

The unit fractions formed by the reciprocals of the values in Sylvester's sequence generate an infinite series: $\sum_{i=0}^{\infty} \frac1{s_i} = \frac12 + \frac13 + \frac17 + \frac1{43} + ...
0
votes
0answers
13 views

Determing sequence from its Dirichlet series

Suppose I know the Dirchlet series $$\sum_{n=1}^{\infty} \frac{f(n)}{n^s} = \frac{\zeta(s)}{\zeta(3s)},$$ where $\zeta(s)$ is the usual Riemann zeta function. My question is - is there a way to ...
0
votes
0answers
9 views

For which n does the inequality $2 \uparrow^{n+1}n > 3\uparrow^n 3 +2$ hold?

For which n does the following inequality hold ? $$2 \uparrow^{n+1}n > 3\uparrow^n 3 + 2$$ where $\uparrow$ stands for knuth's up-arrow notation. I need this inequality to prove that ...
0
votes
2answers
31 views

Is there any use of this mu function?

Let $\nu(\lfloor x\rfloor)$ be the function that gives $0$ if $\sqrt{⌊x⌋}$ isn't irrational, $1$ if $\sqrt{⌊x⌋}$ is an irrational number, and $-1$ if $\sqrt{⌊x⌋}$ is a rational number other than $1$ ...
2
votes
1answer
33 views

Getting multiple of 11

Take any $2$ digit number having different digits. Now add the bigger digit in that number. By continuing this process, you will get a multiple of $11$ i.e. both of the digits will be equal of a ...
2
votes
2answers
215 views

Find last n for which 2^n has a 0.

Find last number $n$ for which $2^n$ has a zero. For example $2^{10}=1024$ has a zero for which last number zero will be there. (It is possible that there doesn't exist such limits to $n$ but what is ...
0
votes
1answer
33 views

$\Bbb Z[i\alpha]$ UFD's

I know that $\Bbb Z[i]$ and $\Bbb Z[\sqrt{-2}]$ are Unique Factorization Domains, and that $\Bbb Z[\sqrt{-6}]$ is not. I have two questions. I know that they may be difficult questions, so I only ask ...
1
vote
1answer
24 views

Asymptotic result about analytic number theory

I don't know if there is any done work done about ehis matter, and I don't have access to research news. I'm interested in this question (I haen't tried to answer it myself, but it seems very ...
3
votes
0answers
31 views

Is there a known method for finding extremely huge squarefree numbers?

People often compete to beat the record for largest known prime (it is currently $2^{57,885,161}-1$). There are also big money prizes for finding explicit prime numbers exceeding specific magnitudes. ...
0
votes
1answer
17 views

Exponential generating function for number of 10 length sequences built from the alphabet, with some restrictions

I've got the following homework question. If anybody could possibly point me in the right direction, that would be great: Suppose X is a sequence with 10 terms built from 26 letters {a, b, c, ..., ...
1
vote
2answers
35 views

A quadratic equation over $\mathbb{Q}_p$

Suppose we have the equation $x^2+x+1$ over the field $\mathbb{Q}_p$. is it possible to determine for what primes $p$ the equation has solutions? I tried to see whether this is related to what $p$ is ...
6
votes
2answers
94 views

Solving $\phi(n)=84$

Ok, I really need some help understanding this because either my brain isn't working at the moment or I'm breaking math and I have a striking suspicion that one of those is more likely. Anyways, ...
1
vote
1answer
19 views

Properties of divisibility

I would like to know if it's true if $a|b$ and $c|d$, then $ac|bd$. I prove in this way: if $a|b$ and $c|d$, then there are $k_1$ and $k_2$, such that $b=k_1a$ and $d=k_2c$, thus $bd=k_1k_2ac$ and ...
0
votes
2answers
58 views

Discrete math: probability of picking certain hands with a preset condition

In 5-card draw poker, a player receives an initial hand of 5 cards, and is then allowed to replace up to three of her cards with the remaining cards in the deck. (b) Suppose that, among the initial 5 ...
1
vote
1answer
33 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
21 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 ...
1
vote
1answer
63 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. ...
2
votes
1answer
44 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
25 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
28 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 ...
0
votes
2answers
19 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
26 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 ...
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
0
votes
1answer
21 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?
2
votes
0answers
63 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
0answers
27 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. ...
1
vote
2answers
62 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
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
43 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.
2
votes
4answers
47 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 ...
1
vote
2answers
41 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
37 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
1answer
26 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
27 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})]$$ ...
0
votes
2answers
16 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
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
47 views
+50

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 ...
2
votes
1answer
68 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. ...
0
votes
0answers
19 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 ...
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 ...
1
vote
1answer
47 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 ...
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?
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
112 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: ...
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
74 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$ ...
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 ...