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
1k views

Complete residue system proof

I was given a proof of this in class, but it does not make sense to me, can someone provide a better proof, or explain the one I have provided, thanks. Suppose $\gcd(a,n) = 1$, where $a$ and $n$ are ...
-4
votes
3answers
333 views

Number of factors proof

Let n be a natural number with d(n) = 33 (number of factors are 33) How would I prove that n and n + 1 don't have a common factor > 1?
4
votes
3answers
429 views

Euclidean Algorithm vs Factorization

Can someone give me an explanation targeted to a high school student as to why finding thegcd of two numbers is faster using the euclidean algorithm compared to using factorization, there should be no ...
2
votes
2answers
191 views

Prove that for any integer $a > 1$ s.t. $\gcd(a, 23) = 1$, $23$ divides $a^{154} - 1$.

Need to use Fermat's Little Theorem (Let $p$ be a prime number and let $a$ be an integer. Then $a^p = a \mod p$. If $p$ does not divide $a$ then $a^p-1 \equiv 1 \mod p$.) $154$ is not prime, but $154 ...
9
votes
4answers
1k views

Proving that an integer is the $n$ th power

I have not been able to solve this problem. Any insights would be appreciated! Let $x, n > 1$ be integers. Suppose that for each $k > 1$ there exists an integer $a_{k}$ such that $x − a_k^n$ is ...
3
votes
4answers
225 views

Show that $\gcd(a,b)=|a| \iff a | b$

I'm reading A Computational Introduction to Number Theory and Algebra, which can be found here as a free download. From the book's exercises, I'm stuck with a proof to show that $\gcd(a,b)=|a| \iff a ...
1
vote
1answer
257 views

Odd positive integers that satisfy $a^2 - b^3 = 4$

Are there any odd positive numbers that satisfy the equation: $a^2 - b^3 = 4$ ? I am certain that there are none but can't prove it. How would you prove that?
1
vote
2answers
110 views

Find $r$ from $x_1\equiv r^a \pmod{p}, x_2\equiv r^b \pmod{p}$ and gcd$(b, p-1)=1$

$r$ is a primitive root for the prime $p$ $x_1\equiv r^a \pmod{p}$ $x_2\equiv r^b \pmod{p}$ If $gcd(b, p-1)=1$, how can I determine $r$ if $p$, $x_2$, and $b$ are known?
3
votes
4answers
321 views

Finding $a,b$ such that $a^{n} + b^{n} $ is $(n+1)^{th}$ power

Can we find all positive integers $a,b$ such that $a^{n}+b^{n}$ is an $(n+1)^{th}$ power? I think this question equivalent to solving the statement $$a^{n} + b^{n} = c^{n+1}$$ for $a,b,c \in ...
2
votes
1answer
191 views

Can this broken proof (of multiplicative of $\varphi$) attempt be fixed?

I wanted to prove that $\varphi$ is multiplicative (that for $(a,b)=1$, $\varphi(ab)=\varphi(a)\varphi(b)$) using the following idea: Define $\varphi'$ by $n = \varphi'(n) + \varphi(n)$. Multiply ...
0
votes
3answers
192 views

formula for number sequence

12, 13, 11, 14, 10, 15, 9, 16... 0, maxNum Start with x then alternate on each side of x until you reach 0 on one side and maxNum on the other. Need to do this in some programming code but can't nail ...
4
votes
1answer
200 views

Limit involving the totient function and combination

Do you think the following limits are correct? $\displaystyle\lim_{d\to\infty}\frac{\sum\limits_{k=1}^{d} {\varphi(N) \choose k} {d-1 \choose k-1}}{\varphi(N)^d}=0$ ...
3
votes
1answer
302 views

Is there a name for this kind of number?

A perfect number is a number that is the sum of its proper divisors: 28 = 1 + 2 + 4 + 7 + 14 Is there a name for numbers whose only proper divisors are 1, 2, and ...
0
votes
2answers
145 views

Conjecture about the set of Sphenic numbers

Sum of a set of sphenic numbers can't be equal to the sum of any other set of sphenic numbers. By that I meant, Say S is the set of sphenic numbers. Let S$_1$ $\subset$ S. Then there is no such ...
6
votes
3answers
952 views

Showing $x^8\equiv 16 \pmod{p}$ is solvable for all primes $p$

I'm still making my way along in Niven's Intro to Number Theory, and the title problem is giving me a little trouble near the end, and I was hoping someone could help get me through it. Now ...
5
votes
1answer
438 views

Continued Fraction of an Infinite Sum

What is the continued fraction for $\displaystyle\sum_{i=1}^n\frac{1}{2^{2^i}}$ It seems to be "almost" periodic, but I can't figure out the exact way to express it.
3
votes
4answers
985 views

Show that a number is not prime?

Show that for any integer $n>1$, all the numbers $n!+2, n!+3, \ldots, n!+n$ are composite (i.e. not prime).
3
votes
1answer
639 views

Algorithms for computing inverse of Euler's phi

I am looking for algorithms that compute the inverse of Euler's totient function.
4
votes
1answer
505 views

Number of Pythagorean Triples under a given Quantity

Consider the function $Pt(n)$. It tells us how many primitive Pythagorean Triples there are (below $n$) when any argument $n \in \mathbb{N}$ is plugged in. Is there an 'exact formula'; i.e. an ...
5
votes
1answer
209 views

Partitioning sets such that the sum of 2 elements is Prime

Given an $n >0$ is it possible to partition the set $\mathcal{P} = \{1,2, \cdots, 2n\}$ into $n$ pairs $(a_{i},b_{i})$ such that $a_{i} + b_{i}$ is a prime?
2
votes
1answer
822 views

Fast algorithm for modular division (residue)

I'm looking for a fast algorithm to perform division of large numbers (by hand). Traditional long division just isn't fast enough for my needs. In most of these cases, I'm only looking for the ...
2
votes
1answer
188 views

Finding the Number of Positive integers such that $\lfloor{\sqrt{n}\rfloor} \mid n$

How does one find the no of positive integers such that find all possible numbers such that $$\lfloor{\sqrt{n}\rfloor} \mid n$$ What i did was to subsitute $n=t^{2}$ so that the equation becomes ...
8
votes
3answers
560 views

Are there addition formulas for the Riemann Zeta function?

In particular for two real numbers $a$ and $b$, I'd like to know if there are formulas for $\zeta (a+b)$ and $\zeta (a-b)$ as a function of $\zeta (a)$ and $\zeta (b)$. The closest I could find ...
3
votes
3answers
281 views

Good Resources for Understanding Finite Field Arithemtic

I am looking for a good reference that could clearly explain finite field arithemtic. Specifically I want to understand the importance and utility of the field generator polynomial and why it is ...
15
votes
3answers
1k views

Are there integer solutions to $9^x - 8^y = 1$?

This came up in proving non-regularity of a certain language (powers of 2 over the ternary alphabet). Any clue to the above equation could help me move forward. Edit: Of course, $x = 1, y = 1$ is a ...
14
votes
2answers
522 views

Have all numbers with “sufficiently many zeros” been proven transcendental?

Any number less than 1 can be expressed in base g as $\sum _{k=1}^\infty {\frac {D_k}{g^k}}$, where $D_k$ is the value of the $k^{th}$ digit. If we were interested in only the non-zero digits of this ...
3
votes
2answers
841 views

$n \mid (a^{n}-b^{n}) \ \Longrightarrow$ $n \mid \frac{a^{n}-b^{n}}{a-b}$

How does one prove that if $n \mid (a^{n}-b^{n}) \ \Longrightarrow$ $ \displaystyle n \mid \frac{a^{n}-b^{n}}{a-b}$ where $a,b, n \in \mathbb{N}$. What i thought of is to consider $$(a-b)^{n} \equiv ...
0
votes
1answer
185 views

Break RSA given a correct and faulty implementation

Suppose I have two machines, $A$ and $B$. $A$ encrypts a message $m$ and outputs the ciphertext $m^e \pmod n$. $B$ outputs $c$ such that $c = m^e \pmod p$ and $c = m^e + 1 \pmod q$. How can I use $A$ ...
0
votes
3answers
532 views

Find x such that $x^2 \equiv 49$ (mod $pq$), $x \not\equiv\pm 7$ (mod $pq$)

Suppose you have two distinct large primes $p$ and $q$. Explain how you can find an integer $x$ such that $x^2 \equiv 49$ (mod $pq$), $x \not\equiv\pm 7$ (mod $pq$).
27
votes
2answers
969 views

Are there infinitely many $x$ for which $\pi(x) \mid x$?

Let $\pi(x)$ denote the Prime Counting Function. One observes that, $\pi(6) \mid 6$, $\pi(8) \mid 8$. Does $\pi(x) \mid x$ for only finitely many $x$, or is this fact true for infinitely many ...
46
votes
1answer
2k views

What's the value of this Viète-style product involving the golden ratio?

One way of looking at the Viète (Viete?) product $${2\over\pi} = {\sqrt{2}\over 2}{\sqrt{2+\sqrt{2}}\over 2}{\sqrt{2+\sqrt{2+\sqrt{2}}}\over 2}\dots$$ is as the infinite product of a series of ...
0
votes
1answer
134 views

Numbers that represent four tuples

Is it possible to make up a distinct number that is made up of four tuples. One of which indicates the direction of the arrangement of the other three. Say, 9*4*7 = 252. 252 is distinct in the sense ...
2
votes
1answer
598 views

Where can I find a list of sphenic numbers?

According to Wikipedia, A Sphenic number is a positive integer which >is the product of three distinct prime numbers. Anybody knows whether there is a list, say first 1000 sphenic numbers? It ...
4
votes
1answer
329 views

Factorial equaling a polynomial

Are there any positive integer solutions $(n,x)$ to the equation $(x)(x+1)=n!$ except $(2,1)$ and $(3,2)$? If not (as I suspect is the case), how do you prove that? In general, is there a way to ...
9
votes
3answers
484 views

Theorem on natural density

In this answer to a question about a series, a theorem was stated: if $A= \{a_i \}$ is a set such that $\sum_{i = 1}^{\infty} \frac{1}{a_i}$ converges, then $d(A) = 0$, where $d(A)$ is the natural ...
6
votes
3answers
1k views

Integral solutions to $y^{2}=x^{3}-1$

How to prove that the only integral solutions to the equation $$y^{2}=x^{3}-1$$ is $x=1, y=0$. I rewrote the equation as $y^{2}+1=x^{3}$ and then we can factorize $y^{2}+1$ as $$y^{2}+1 = (y+i) \cdot ...
2
votes
2answers
250 views

Prime divisibility

I have the following assertion in my notes from last year that I'm trying hard to digest, but I think it isn't true: If $p$ is prime $\Leftrightarrow$ if $p | ab$ then either $p | a$ or $p | b$ or ...
20
votes
6answers
4k views

Efficiently finding two squares which sum to a prime

The web is littered with any number of pages (example) giving an existence and uniqueness proof that a pair of squares can be found summing to primes congruent to 1 mod 4 (and also that there are no ...
8
votes
7answers
1k views

Proving ${n \choose p} \equiv \Bigl[\frac{n}{p}\Bigr] \ (\text{mod} \ p)$

This is an exercise from Apostol, which i have been struggling for a while. Given a prime $p$, how does one show that $${n \choose p} \equiv \biggl[\frac{n}{p}\biggr] \ (\text{mod} \ p)$$ Note that ...
4
votes
4answers
377 views

For any positive integers $a,b$, one has $a^4|b^3$ implies $a|b$?

This is an old exam problem I found online. For any positive integers $a,b$, one has $a^4|b^3$ implies $a|b$. Clearly if $a^4|b^3$, then $a|b^3$. It seemed simple on first reading, but I can't figure ...
3
votes
1answer
124 views

System of Congruences

Suppose $x_1, x_2, y_1, y_2$ are known integers which satisfy $y_1 \equiv \gamma x_1 \pmod c$ and $y_2 \equiv \gamma x_2 \pmod c$ where $\gamma$ and $c$ are unknown integers. Is there a way to ...
5
votes
2answers
855 views

Generalizing values which Euler's-totient function does not take

I was reading about Euler's totient function on wikipedia, and it eventually led me to this book on google: Page 74 of the book, Prime numbers: the most mysterious figures in math By David G. Wells. ...
3
votes
2answers
213 views

Recurrence relation for $a_{n}$ where $6a_{n}$ and $10a_{n}$ are both triangular

According A180926, the elements of the set {$a:\exists m,n|60a=5n^2+5n=3m^2+3m$} satisfy the following recurrence relation: $$a_{n}=\frac{62a_{n-1}+1+\sqrt{(48a_{n-1}+1)(80a_{n-1}+1)}}{2}$$ ...
6
votes
2answers
452 views

A triangular representation for the divisor summatory function, $D(x)$

Let $d(n)$ represent the divisor function as $d(n)=\displaystyle\sum\limits_{k|n}1$ and the divisor summatory function as $D(x)=\displaystyle\sum\limits_{n \leq x}d(n)$ I found the following ...
8
votes
3answers
706 views

Why are some mathematical constants irrational by their continued fraction while others aren't?

Catalan's Constant and quite a few other mathematical constants are known to have an infinite continued fraction (see the bottom of that webpage). On wikipedia (I'm sorry, I can't post anymore ...
6
votes
4answers
618 views

$k^{2}+(k+1)^{2}$ being a perfect square for infinitely many $k$

Generally one can see that there are infinite number of solutions for this equation $$a^{2}+b^{2}=c^{2}$$ by taking multiples of the solution $3,4$ and $5$. Can i use this as a fact to prove, that ...
3
votes
1answer
430 views

Prime Number theorem and the prime counting function

Could someone please help me understand this proof given in an article by William Miller its supposed to follow from the prime number theorem that given, $A(x)$ which is the sum of all primes less ...
2
votes
3answers
843 views

Perfect numbers, the pattern continues

The well known formula for perfect numbers is $P_n=2^{n-1}(2^{n}-1)$ this formula is obtained by observing some patterns on the sum of the perfect number's divisors. Take for example $496$ ...
2
votes
2answers
495 views

How can I find out whether a number is a quadratic residue in a large modulo?

Without strenuous arithmetic. Is there a program I can download to do so? What are the quadratic residues modulo $5^4$ or $5^5$? Thanks!
12
votes
6answers
12k views

Determine whether a number is prime

How do I determine if a number is prime? I'm writing a program where a user inputs any integer and from that the program determines whether the number is prime, but how do I go about that?