Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.
8
votes
5answers
886 views
Prove a number is composite
How can I prove that $$n^4 + 4$$ is composite for all $n > 5$?
This problem looked very simple, but I took 6 hours and ended up with nothing :(. I broke it into cases base on quotient remainder ...
8
votes
3answers
443 views
The last two digits of $9^{9^9}$
I tried to calculate the last two digits of $9^{9^9}$ using Euler's Totient theorem, what I got is that it is same as the last two digits of $9^9$.
How do I proceed further?
8
votes
3answers
4k views
Is there a formula to calculate the sum of all proper divisors of a number?
I don't need to list all proper divisors, I just want to get its sum. Because for a small number, checking all proper divisors and adding them up is not a big deal. However, for a large number, this ...
8
votes
5answers
461 views
Questions about composite numbers
Consider the following problem:
Prove or disprove that if $n\in \mathbb{N}$, then $n$ is prime iff $$(n-1)!+n$$ is prime.
If $n$ is composite and greater than $1$, then $n$ have a divisor less than ...
8
votes
11answers
4k views
Proof that $n^3+2n$ is divisible by 3
I'm trying to freshen up for school in another month, and I'm struggling with the simplest of proofs!
Problem:
For any natural number n , n3 + 2n is divisible by 3.
This makes sense
...
8
votes
1answer
331 views
Can $x^{n}-1$ be prime if $x$ is not a power of $2$ and $n$ is odd?
Are there any solutions to $x^{n}-1=p$ with p prime, integers $x,n>1$ and $x$ not a power of $2$?
$x$ must be even. $n$ is odd since if $n=2m$ then $p=x^{n}-1=(x^{m}+1)(x^{m}-1)$ hence $p=x^{m}+1$ ...
8
votes
3answers
301 views
How are the integral parts of $(9 + 4\sqrt{5})^n$ and $(9 − 4\sqrt{5})^n$ related to the parity of $n$?
I am stuck on this question,
The integral parts of $(9 + 4\sqrt{5})^n$ and $(9 − 4\sqrt{5})^n$ are:
even and zero if $n$ is even;
odd and zero if $n$ is even;
even and one if $n$ is ...
8
votes
3answers
550 views
Is there a “nice” formula for $\sum_{d|n}\mu(d)\phi(d)$?
I'm trying to work through Ireland and Rosen's A Classical Introduction to Modern Number Theory as I've heard good things about it. This is Exercise 12 from Chapter 2. Here $\mu$ is the Moebius ...
8
votes
5answers
196 views
How can I find the possible values that $\gcd(a+b,a^2+b^2)$ can take, if $\gcd(a,b)=1$
If $\gcd(a,b)=1$, how can I find the values that $\gcd(a+b,a^2+b^2)$ can possibly take? I can´t find a way to use any of the elemental divisibility and gcd theorems to find them.
8
votes
4answers
795 views
If $\gcd( a, b ) = 1$, then is it true to say $\gcd( ac, bc ) = c$?
I tried to prove this theorem, but I'm really confused about its correctness.
Let's say
$$\gcd( a, b ) = 1 \Rightarrow am + bn = 1 \text{ where } m, n\in\mathbb Z$$
Then by multiplying both side ...
8
votes
2answers
231 views
On Pythagorean Triplets
The Problem: In the Pythagorean triplets (a,b,c) when a < b then b can't be a prime number.
The Background: While searching the properties of Pythagorean triplets in web I saw quite a few listed, ...
8
votes
3answers
159 views
If $\gcd(a,35)=1$ then show that $a^{12} \equiv 1 \pmod{35}$
If $\gcd(a,35)=1$, then show that $a^{12}\equiv1\pmod{35}$
I have tried this problem beginning with $a^6 \equiv 1 \pmod{7}$ and $a^4 \equiv 1 \pmod{5}$ (Fermat's Theorem) but couldn't get far ...
8
votes
2answers
570 views
Why does $\phi(pq)=\phi(p)\phi(q)$?
In an RSA paper I am reading it is assumed that where $p$ and $q$ are distinct prime numbers:
$\phi(pq)=\phi(p)\phi(q)=(p-1)(q-1)$
I would love to know why/how this is so? Is there some way to prove ...
8
votes
3answers
215 views
$(n!+1,(n+1)!)$ hints for finding gcd.
$(n!+1,(n+1)!)$ can be rewritten as $(n!+1,(n+1)*n!)$.
I know that if $n!$ is divisible by a prime $p$ then $p$ doesn't divide n!+1.
So when I'm looking at then is $(n!+1 , n+1)$ which I can make ...
8
votes
3answers
568 views
Motivation behind the definition of GCD and LCM
According to me, I can find the GCD of two integers (say $a$ and $b$) by finding all the common factors of them, and then finding the maximum of all these common factors. This also justifies the ...
8
votes
3answers
156 views
Number theory: Prime powers and cubes
Determine all triples $(p,a,b)$ of positive integers, where $p$ is prime and $a \leq b$ such that $$p^a+p^b$$ is a perfect cube.
I came across this question while looking at past maths Olympiad ...
8
votes
3answers
197 views
Prove $\left \lfloor \frac{1}2 \left( 2+\sqrt3 \right) ^{2002} \right\rfloor \equiv -1 \pmod7 $
Prove
$$ \large \left\lfloor \frac{1}2 \left( 2+\sqrt3 \right) ^{2002} \right\rfloor \equiv -1 \pmod7 $$
So far my intuion only tells me that this has something to do with $(2+\sqrt3)(2-\sqrt3)=1$, ...
8
votes
4answers
590 views
Prime Partition
A prime partition of a number is a set of primes that sum to the number. For instance, {2 3 7} is a prime partition of $12$ because $2 + 3 + 7 = 12$. In fact, there ...
8
votes
4answers
968 views
Looking to understand the rationale for money denomination
Money is typically denominated in a way that allows for a greedy algorithm when computing a given amount $s$ as a sum of denominations $d_i$ of coins or bills:
$$
s = \sum_{i=1}^k n_i ...
8
votes
3answers
142 views
Does $a^n \mid b^n$ imply $a\mid b$?
Does $a^n \mid b^n$ imply $a\mid b$? I think it does but haven't been able to prove it.
I don't know much number theory so an elementary answer would be great.
8
votes
4answers
278 views
question about division
The question is from the following two problems:
Let $x$ and $y$ be positive integers such that $3x+7y$ is divisible by $11$. Which of the following must also be divisible by $11$?
A. $4x+6y$ ...
8
votes
2answers
370 views
How can my proof be improved? “Let $n$ be an integer. If $3n$ is odd then so is $n$.”
I am attempting to self-study proof techniques and your criticism of my following proof would be greatly appreciated. Feel free to nitpick minor/trivial things; that's how I'll learn!
Edit: I have ...
8
votes
2answers
144 views
Compute the remainder when $67!$ is divided by $71$.
This is how far I've been able to get.
By using Wilson's Theorem:
$$\begin{align}
70! &\equiv -1 \pmod{71} \\
67!(68)(69)(70) &\equiv -1 \pmod{71} \\
67!(68)(69)(-1) &\equiv -1 \pmod{71} ...
8
votes
3answers
186 views
Proof of Wolstenholme's theorem.?
According to the theorem :
$$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+...+\frac{1}{p-1} =\frac{r}{q}$$
And we have to prove that $r= 0 \pmod{p^2}$.
(Given $ p>3$, ...
8
votes
1answer
121 views
Pretty solution to question about floor function
I was recently asked this question by a student, and I don't know a nice, elegant way to solve it (actually, I'm not sure I know how to solve it at all).
Let $S(\alpha)=\lbrace \lfloor ...
8
votes
2answers
405 views
On proof of AKS primality test algorithm
Just studying the paper PRIMES is in P, although I've tried great efforts, some proofs are still not so clear(or obvious) to me, especially the proof of ...
8
votes
4answers
240 views
prove sum of divisors of a square number is odd
Don't know how to prove that sum of all divisors of a square number is always odd.
ex: $27 \vdots 1,3,9,27$; $27^2 = 729 \vdots 1,3,9,27,81,243,729$; $\sigma_1 \text{(divisor
function)} = 1 + 3 + 9 ...
8
votes
3answers
430 views
Find all odd primes $p$ for which $15$ is a quadratic residue modulo $p$
I want to find all odd primes $p$ for which $15$ is a quadratic residue modulo $p$.
My thoughts so far: I want to find $p$ such that $ \left( \frac{15}{p} \right) = 1$. By multiplicativity of the ...
8
votes
1answer
108 views
Why cannot $2^x=m^n+1$?
$x,n,m >1$ and $x,n,m \in \mathbb{Z}$
I've tried to solve it myself, but I'm getting nowhere, so apologies if it's an irritatingly basic question.
Whilst I'm on it, is it true that $y^x \ne ...
8
votes
1answer
156 views
Do roots of a polynomial with coefficients from a Collatz sequence all fall in a disk of radius 1.5?
Consider a modified version of Collatz sequence:
$C(n)=\left\{ \begin{array}{ll} \frac{3n+1}{2} & n\ \mathrm{odd} \\ \frac{n}{2}& n\ \mathrm{even}\end{array} \right.$
Let $F_n$ be the ...
8
votes
3answers
606 views
If an integer is not divisible by 2 or 5
I have found this statement ,can you help me to prove this.
If an integer is not divisible by 2 or 5, some multiple of that number in decimal notation is a sequence of only a digit.
OBJECTIVE: Now ...
8
votes
3answers
166 views
$a+b=c \times d$ and $a\times b = c + d$
There is a 'nice' relationship between the integers (1,5) and (2,3) as
$$1+5=2 \times 3;$$
$$1\times 5 = 2 + 3.$$
So I tried to find all positive integers pairs $(a, b)$ and $(c, d)$ such that ...
8
votes
2answers
440 views
Basic divisibility fact
I'm trying to prove "the following generalization of Theorem 5 [ Th.5: if $a|bc$ and $(a,b)=1$ then $a | c$ ], which uses the same argument for its proof" (Sierpinski, The Theory of Numbers): if $a$, ...
8
votes
2answers
115 views
For which $n$ is $n\sigma(n)\equiv 2 \pmod {\phi(n)}$?
How to find all of $n \in \Bbb N$ such that: $$n\sigma(n)\equiv 2 \pmod {\phi(n)}$$
$\sigma(n)$ is summation of all distinct divisors of $n$
For $p$ prime we have: $p(p+1)=p^2+p\equiv 2 \pmod {p-1}$
...
8
votes
5answers
233 views
How can I compute the sum of $ {m\over\gcd(m,n)}$?
$$ \sum_{m =1}^n {m\over\gcd(m,n)}$$
For example,
for 1 it is
$${1\over\gcd(1,1)} =1;$$
for 5 it is
$${1\over \gcd(1,5)}+{2\over \gcd(2,5)}+{3\over \gcd(3,5)}+{4\over \gcd(4,5)}+{5\over ...
8
votes
2answers
61 views
Are the high-order bits of $n^2$ as likely to be zeroes as ones?
Let $B_i(n)$ be the $i$th bit in the binary expansion of $n$, so that $n=\sum B_i(n)2^i$. Now let $n$ be randomly and uniformly chosen from some large range, and let $E(j)$ be the expected value of ...
8
votes
1answer
185 views
Prove that if $\sigma(n)=2n+1$ then $n$ is an odd perfect square.
Prove that if $\sigma(n)=2n+1$ then $n$ is an odd perfect square.
(Here, $\sigma(n)$ is the sum of the positive divisors of $n$
including 1 and $n$ itself.)
As I know, this $n$ is a quasiperfect ...
8
votes
1answer
97 views
Proving a number defined by a sequence is a square number
I found this problem in a math magazine:
Given the sequence $(x_n)_{n \in \mathbb{N}}$ defined by:
$$
x_0 = 0\\
x_1 = 1\\
x_{n+2}+x_{n+1}+2x_{n}=0
$$
Prove that $s_n = 2^{n+1}-7x_{n-1}^2, n ...
8
votes
2answers
174 views
How to find all naturals $n$ such that $\sqrt{1 {\underbrace{4\cdots4}_{n\text{ times}}}}$ is an integer?
How to find all naturals $n$ such that $\sqrt{1\smash{\underbrace{4\cdots4}_{n\text{ times}}}}$ is an integer?
8
votes
2answers
350 views
Value of cyclotomic polynomial evaluated at 1
Let $\Phi_n$ be the usual cyclotomic polynomial (minimal polynomial over the rationals for a primitive nth root of unity).
There are many well-known properties, such as $x^n-1 = \Pi_{d|n}\Phi_d$.
...
8
votes
2answers
256 views
Number of zeros not possible in $n!$ [duplicate]
Possible Duplicate:
How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes?
The number of zeros which are not possible at the end of the $n!$ is:
...
8
votes
1answer
147 views
Sum of square root of primes
I was playing around with prime numbers and a question came into my mind:
Let $S(n)$ denote the sum of square roots of primes from $2$ to the $n$th prime number.
Are there infinitely many numbers $n$ ...
8
votes
4answers
165 views
Prove that if $a$ and $b$ are odd, coprime numbers, then $\gcd(2^a +1, 2^b +1) = 3$
Prove that if $a$ and $b$ are odd, coprime numbers, then $\gcd(2^a +1, 2^b +1) = 3$.
I was thinking among the lines of:
Since $a$ and $b$ are coprime numbers, $\gcd(a,b)=1$. Then there exist ...
8
votes
2answers
48 views
Having $A_1=a+b+c$,$A_2=a^2+b^2+c^2$, $A_3=a^3+b^3+c^3$ - how to get $a,b,c$?
Perhaps I'm just a bit dense at the moment - I've re-read some of my notes from monthes ago concerning elementary symmetric polynomials, and I find that I've no idea how to approach the "inverse" ...
8
votes
4answers
168 views
Representing a number as a sum of at most $k$ squares
Fix an integer $k >0 $ and would like to know the maximum number of different ways that a number $n$ can be expressed as a sum of $k$ squares, i.e. the number of integer solutions to
$$ n = x_1^2 + ...
8
votes
1answer
98 views
Möbius function from random number sequence
Consider some arbitrary number sequence like the decimal expansion of $\pi$ = {3, 1, 4, 1, 5, 9, 2}. Prepend the sequence with the number $1$ so that you get {1, 3, 1, 4, 1, 5, 9, 2}.
Then plug it ...
8
votes
1answer
108 views
Summing over a cyclic subgroup of a multiplicative group mod n
Let $x$ be a unit in $\mathbb Z/ n \mathbb Z$ of multiplicative order $m$.
I am trying to determine when it is that
$$
\sum_{i=0}^{m-1} x^i \equiv 0 \mod n .
$$
Is this kind of situation something ...
8
votes
3answers
223 views
Why does $a^n - b^n$ never divide $a^n + b^n$?
I'm working through the problems in Niven's number theory book, and problem 46 in section 1.2 (page 19) has me stumped.
Prove that there are no positive integers $a, b, n > 1$ such that $(a^n - ...
8
votes
0answers
218 views
Understanding Ramanujan's approach in his proof of Bertrand's Postulate
I've been reading through Ramanujan's proof of Betrand's Postulate and I'm not clear why he didn't state his proof in terms of $\varphi(2x) - \varphi(x)$
What would be wrong with this approach for ...
8
votes
0answers
312 views
Is it possible to find the digit sum of $n!$ ($n \in \mathbb{N} \text{ and } n \le100$) without actually computing the factorial?
Is it possible to find the digit sum of $n!$ ($n \in \mathbb{N} \text{
and } n \le100$) without actually computing the factorial?
I faced this problem in quantitative aptitude test which asks ...
