This tag is for questions about divisibility, that is, determining when one thing is a multiple of another thing.

learn more… | top users | synonyms

16
votes
2answers
888 views

Proving there are an infinite number of pairs of positive integers $(m,n)$ such that $\frac{m+1}{n}+\frac{n+1}{m}$ is a positive integer

The question is: Show that there are an infinite number of pairs $(m,n): m, n \in \mathbb{Z}^{+}$, such that: $$\frac{m+1}{n}+\frac{n+1}{m} \in \mathbb{Z}^{+}$$ I started off approaching this ...
12
votes
2answers
1k views

Elementary proof of Zsigmondy's theorem

I've been writing a not-so-short introduction to elementary number theory, supplying proofs for all theorems. When coming across Zsigmondy's theorem, it seemed difficult to find a proof available on ...
2
votes
4answers
174 views

Division of $q^n-1$ by $q^m-1$, in Wedderburn's theorem

I need this for a proof of Wedderburn's theorem: $$q^m - 1 | q^n - 1 \quad \Rightarrow \quad m|n$$ with $q>1 \in \mathbf{N}$ and $m,n \in \mathbf{N}$. I'd also like to know if it works the other ...
9
votes
3answers
394 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.
2
votes
3answers
202 views

Prove that distinct Fermat Numbers are relatively prime [duplicate]

The Fermat numbers are defined by $F_m = 2^{2^m} + 1$. Prove that for $m \ne n$ we have $(F_m, F_n) = 1$. I have to first prove that $F_{m+1} = F_0F_1 \cdots F_m + 2$ by representing $F_{m+1}$ in ...
2
votes
3answers
114 views

Divisor in $\mathbb{C}[X]$ $\implies$ divisor in $\mathbb{R}[X]$?

let $P \in \mathbb{R}[X]$ be a real polynomial divisible by a polynomial $Q \in \mathbb{R}[X]$ in $\mathbb{C}[X]$. How can I easily show that $P$ is also divisible by $Q$ in $\mathbb{R}[X]$? A simple ...
11
votes
2answers
249 views

Show that $A[X]/(aX+b)$ is an integral domain

Let $A$ be an integral domain, $a$ and $b \in A-\{0\}$, and let $B = A[X]/(aX+b)$. Show that, if $Aa \cap Ab=Aab$, then $B$ is an integral domain. My attempt at proof (following a hint). Denote ...
5
votes
3answers
2k views

If $2^n - 1$ is prime from some integer $n$, prove that n must also be prime.

I understand the idea of the proof. I just want to make sure I wrote my proof well. Suppose $n$ is not prime. Then $\exists x,y \in \mathbb{Z}$ such that $n = xy$. $2^{xy} - 1 = (2^x)^y - 1$ $ = ...
4
votes
5answers
182 views

If $\gcd(a,b)=1$ then, $\gcd(a^2,b^2)=1$ [duplicate]

Prove or disprove 'If $\gcd(a,b)=1$ then, $\gcd(a^2,b^2)=1$, with $a,b\not= 0$' I need to prove this statement. I think it is true and also the converse is true. I took some examples such as ...
3
votes
3answers
100 views

Let $a,b$ be positive integers such that $a\mid b^2 , b^2\mid a^3 , a^3\mid b^4 \ldots$ so on , then $a=b$?

Let $a,b$ be positive integers such that $a\mid b^2 , b^2\mid a^3 , a^3\mid b^4 \ldots$ that is $a^{2n-1}\mid b^{2n} ; b^{2n}\mid a^{2n+1} , \forall n \in \mathbb Z^+$ , then is it true that $a=b$ ?
0
votes
3answers
1k views

How to show that $\gcd(n! + 1, (n + 1)! + 1) \mid n$?

Let $n$ be a positive integer, $n!$ denotes the factorial of $n$. Let $d = \gcd(n! + 1, (n + 1)! + 1)$. Show that $d$ divides $n$. (Hint: notice that $(n+1)(n!+1) = (n+1)!+n+1$)
4
votes
3answers
429 views

Prove that $(a+1)(a+2)…(a+b)$ is divisible by $b!$ [duplicate]

The problem is following, prove that: $$(a+1)(a+2)...(a+b)\text{ is divisible by } b!\text{ for every positive integer a,b}$$ I've tried solving this problem using mathematical induction, but I ...
4
votes
4answers
473 views

Proving that $ \gcd(a,b) = as + bt $, i.e., $ \gcd $ is a linear combination.

For any nonzero integers $ a $ and $ b $, there exist integers $ s $ and $ t $ such that $ \gcd(a,b) = as + bt $. Moreover, $ \gcd(a,b) $ is the smallest positive integer of the form $ as + bt $. I ...
3
votes
1answer
1k views

Prove the converse of Wilson's Theorem

... namely that if $n > 1$ and $(n − 1)!\equiv−1\pmod{n}$, then $n$ is prime. This is for a number theory class I'm in at Penn State. My idea is to follow accordingly, but I can't get it ...
2
votes
3answers
163 views

The number $n^4 + 4$ is never prime for $n>1$

I am taking a basic algebra course, and one of the proposed problems asks to prove that $n^4 + 4$ is never a prime number for $n>1$. I am able to prove it in some particular cases, but I am not ...
1
vote
2answers
63 views

If I remove the premise $a\neq b$ in this question, will the statement still be true?

I encountered this proving problem, I can do the proof but my question is why in the condition/premise we need $a$ to be unequal to $b$? My guess is that even $a=b$, the statement is still true, is it ...
1
vote
5answers
302 views

$24\mid n(n^{2}-1)(3n+2)$ for all $n$ natural problems in the statement.

"Prove that for every $ n $ natural, $24\mid n(n^2-1)(3n+2)$" Resolution: $$24\mid n(n^2-1)(3n+2)$$if$$3\cdot8\mid n(n^2-1)(3n+2)$$since$$n(n^2-1)(3n+2)=(n-1)n(n+1)(3n+2)\Rightarrow3\mid ...
0
votes
1answer
123 views

Division rules for other number systems? [duplicate]

How could we make the same division rules for other number systems, like in our decimal system: a number is divisible with 2 if it's last digit is 0,2,4,6,8, by 3 if the sum of digits is divisible ...
0
votes
5answers
191 views

Proving that if $\;5\mid(a+11)\;$ and $\;5\mid(16-b),\;$ then $\;5\mid(a+b)$

Can you please help me a bit with this question? How do we show that $\;$ if $\;\;5\mid(a+11)\;$ and $\;5\mid(16-b),\;\;$ then $\;5\mid(a+b)\;$? Thanks a lot!
37
votes
4answers
2k views

How does the divisibility graphs work?

I came across this graphic method for checking divisibility by $7$. $\hskip1.5in$ Write down a number $n$. Start at the small white node at the bottom of the graph. For each digit $d$ in ...
13
votes
2answers
295 views

Prove $6 \nmid [\left( \sqrt[3]{28} - 3 \right)^{-n}]$

Prove that: $$6 \not\left|\ \left\lfloor\frac 1 {(\sqrt[3]{28} - 3)^{n}}\right\rfloor \ (n \in Z^+)\right.$$ ($\lfloor x\rfloor$ = largest integer not exceeding $x$) I am very bad as English and ...
34
votes
8answers
3k views

What is $\gcd(0,0)$?

What is the greatest common divisor of $0$ and $0$? On the one hand, Wolfram Alpha says that it is $0$; on the other hand, it also claims that $100$ divides $0$, so $100$ should be a greater common ...
9
votes
3answers
727 views

How many 0's are in the end of this expansion?

How many $0's$ are in the end of: $$1^1 \cdot 2^2 \cdot 3^3 \cdot 4^4.... 99^{99}$$ The answer is supposed to be $1100$ but I have absolutely NO clue how to get there. Any advice?
11
votes
2answers
838 views

What is the remainder when $1! + 2! + 3! +\cdots+ 1000!$ is divided by $12$?

What is the remainder when $$1! + 2! + 3! +\cdots+ 1000!$$ is divided by $12$. I have tried to find the answer using the Binomial Theorem but that doesn't help. How will we do this? Please help.
11
votes
2answers
613 views

Does $n \mid 2^{2^n+1}+1$ imply $n \mid 2^{2^{2^n+1}+1}+1$?

There are two ways to try to prove this. One is in the title, the other is its de Morgan counterpart: $n \nmid 2^{2^{2^n+1}+1}+1 \implies n \nmid 2^{2^n+1}+1$. Disproving it requires only one example ...
5
votes
1answer
188 views

Prove Divisibility In Fibonacci Sequence Over A Prime Number

In The Fibonacci sequence which is defined as: Lets say we have the number $p$ which is an odd prime. Prove that: $F_{p-1} + F_{p+1} -1$ Is divisible by $p$. Prove that for any given $n$ real ...
2
votes
3answers
104 views

$\dfrac1a+\dfrac1b=\dfrac1c$, $a, b, c \in \mathbb{N}$ with no common factor, find all solutions [duplicate]

Given $\dfrac1a+\dfrac1b=\dfrac1c$, where $a, b, c \in \mathbb{N}$ with no common factor, find all solutions. Actually, you can think this question as a follow up of this one. Today, I saw this ...
1
vote
2answers
89 views

Divisibility of sum of powers: $\ 323\mid 20^n+16^n-3^n-1\ $ for which $n?$

I found this question in my Math Challenge II Number Theory packet: Find all positive integers $n$ that satisfy $323|20^n+16^n-3^n-1$. I don't even have any idea how to approach this question. Any ...
9
votes
11answers
492 views

3 never divides $n^2+1$

Problem: Is it true that 3 never divides $n^2+1$ for every positive integer n? Explain. Explanation: If n is odd, then $n^2+1$ is even. Hence 3 never divides $n^2+1$, when n is odd. If n is even, ...
3
votes
1answer
74 views

Determine the divisibility of a given number without performing full division

My question is slightly more complicated than what's implied on the title, so I will start with an example. Given any number $N$ on base $10$, we can easily determine whether or not $N$ is divisible ...
3
votes
3answers
602 views

Number of divisors

How can I find number of divisors of N which are not divisible by K. ($2 \leq N$, $k \leq 10^{15})$ One of the most easiest approach which I have thought is to first calculate total number of ...
2
votes
1answer
123 views

If $m,n\in \mathbb N$ and $n>m$, prove that $\text{lcm}(m,n)+\text{lcm}(m+1,n+1)>\frac{2mn}{\sqrt{n-m}}$.

Where $\text{lcm}$ is the least common multiple. I've changed it to: $$\frac{mn}{\gcd(m,n)}+\frac{(m+1)(n+1)}{\gcd(m+1,n+1)}>\frac{2mn}{\sqrt{n-m}}$$ Can't see how to continue. Is there a way to ...
1
vote
2answers
106 views

Proving a Pellian connection in the divisibility condition $(a^2+b^2+1) \mid 2(2ab+1)$

I'm trying to prove that all integer solutions $a > b \ge 0$ to the divisibility condition in the title, namely $$(a^2+b^2+1) \mid 2(2ab+1),$$ are given by ...
9
votes
6answers
264 views

Understanding the proof of a formula for $p^e\Vert n!$

This is a proof from a book on number theory I'm reading. I'm having a hard time following. I think there's a variable here that means two different things at two different times... Theorem: If n is ...
8
votes
4answers
121 views

Show that $15\mid 21n^5 + 10n^3 + 14n$ for all integers $n$.

I'm not sure if it's correct, but what I have so far is; $$21n^5 + 10n^3 + 14n ≡ (1 + 0 - 1) ≡ 0 \mod 5$$ but I'm having trouble solving it in $\bmod 3$. I have: $$21n^5 + 10n^3 + 14n ≡ (0 + (?) + ...
8
votes
1answer
773 views

Smallest number with a given number of factors

From my rather rudimentary explorations of this fascinating problem, I believe it to be a layered and rewarding subject for investigation. My question, essentially, is: How do you find the smallest ...
6
votes
3answers
14k views

Find the largest prime factor

I just "solved" the third Project Euler problem: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? With this on Mathematica: ...
5
votes
5answers
804 views

Divisibility by 7

What is the fastest known way for testing divisibility by 7? Of course I can write the decimal expansion of a number and calculate it modulo 7, but that doesn't give a nice pattern to memorize because ...
5
votes
4answers
3k views

How to prove gcd of consecutive Fibonacci numbers is 1? [duplicate]

Possible Duplicate: Prove that two any consecutive terms of Fibonacci sequence are relatively prime How to prove it ? Can you help me ? Let $f_n$ be Fibonacci Sequence. ...
4
votes
5answers
84 views

$p$ divides $n^p-n$

Its very easy to prove $p\mid n^p-n$ for p=3,5,7, it fails for p=9 because $$ (n+1)^9-(n+1)= n^9+9n^8+36n^7+84n^6+126n^5+126n^4+84 n^3+36n^2+8n $$ and $84= 2²\times 3\times7$. Is it true for ...
4
votes
2answers
3k views

Proof of $\gcd(a,b)=ax+by$

Here is my proof of $\gcd(a,b)=ax+by$ for $a, b, x, y \in \mathbb{Z}$. Am I doing something wrong? Are there easier proofs? $a,b \in \mathbb{Z}, g=\gcd(a,b)$ and suppose $g \neq ax + by$. Let $c$ be ...
3
votes
2answers
72 views

$f,g,h$ are polynomials. Show that…

Let $f,g$ and $h$ be polynomials. Show that $\gcd(f,g,h)=\gcd(\gcd(f,g),h)$. I was thinking of signing $\gcd(f,g)=d$ and then write it by using Euclid's algorithm, but I couldn't get anything proper. ...
3
votes
1answer
83 views

Values of $\gcd(a-b,\frac{a^p-b^p}{a-b} )$

I don't know how to prove the following result. Let $p$ be a prime number and let $a,b \in \mathbb Z$ such that $\gcd(a,b)=1$ Then $\gcd (a-b,\frac{a^p-b^p}{a-b}) = 1 $ or $ p $ (gcd should be ...
3
votes
1answer
1k views

Sum of GCD(k,n)

I want to find this $$ \sum_{k=1}^n \gcd(k,n)$$ but I don't know how to solve. Does anybody can help me to finding this problem. Thanks.
2
votes
2answers
122 views

Find all primes of the form $2^{2^n} + 5$ for a nonnegative integer n

I'm a little lost on how to do this problem. It looks a lot like the definition for the Fermat numbers: $F_n = 2^{2^n} + 1$, however I'm not sure how to use that in order to find all of the primes of ...
2
votes
2answers
140 views

Proving $\phi(m)|\phi(n)$ whenever $m|n$ [duplicate]

Show that $\varphi(m)|\varphi(n) $ whenever $m|n$. I am stuck after writing the formula. I know that if $m$ divides $n$, that means one of the prime factors of $n$ would include $m$ or a multiple of ...
2
votes
5answers
127 views

How to show $n(n+1)(2n+1) \equiv 0 \pmod 6$?

I've been asked to show that: $n(n+1)(2n+1) \equiv 0 \pmod 6$ I found in a previous question that: $n(n+1)$ was divisible by $2$ and resulted in an even number e.g $n(n+1) \equiv 0 \pmod 2$ so I ...
2
votes
2answers
146 views

Asymptotic divisor function / primorials

Let $p_n\#\equiv\prod_{k=1}^{n}p_k$ (primorial), and $\sigma(n)=\sum_{d|n}^{}d$ (divisor function). Could someone please tell me what the general asymptotic of $\dfrac{\sigma(p_n\#)}{p_n\#}$ is? It ...
2
votes
4answers
181 views

Prove the following: If $a \mid bc$, then $a \mid \gcd(a, b)c$.

Prove the following: If $a \mid bc$, then $a \mid \gcd(a, b)c$. I tried to set $\gcd(a, b)$ to $b$ and used the fundamental theorem of arithmetic to prove that it is divisible by $a$, but I ...
2
votes
3answers
114 views

System of two simple modular equations

$$x \equiv -7 \mod 13$$ $$x \equiv 39 \mod 15$$ I need to find the smallest x for which these equations can be solved. I've been always doing this using Chinese Reminder Theorem, but it seems that it ...