# Tagged Questions

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

41 views

### Simple equation - prove division

this should be simple. I am helping my son with one assignment but I simply cannot solve it. I really exhausted ideas. The problem is: prove that $\displaystyle {(m^2 + 5m)(m^2 + 5m + 10) + 24}$ can ...
62 views

### Are there a closed form of near solutions to the equation: $2\sigma(n)=3n$? [closed]

I would like to check the solution of this equation: $$2\sigma(n)=3n$$ where $\sigma(n)$ is the sum divisor function. Note: I know only $n=2$ is a theortitical solution, are there a closed form of ...
29 views

### Suppose $d$ is a common divisor of two numbers $a_0$ and $a_1$, can $d$ be written as a linear combination of $a_0$,$a_1$ with integer coefficients?

Suppose $d$ is a common divisor of two numbers $a_0$ and $a_1$, can $d$ be written as a linear combination of $a_0$,$a_1$ with integer coefficients? i.e. there exists two integers $i_0,i_1 \in \Bbb Z$ ...
2k views

### Relationship between Primes and Fibonacci Sequence

I recently stumbled across an unexpected relationship between the prime numbers and the Fibonacci sequence. We know a lot about Fibonacci numbers but relatively little about primes, so this connection ...
54 views

### Prove that $τ(m^n)$ and $n$ are coprime $(m,n ∈ N^+)$

We have that $τ(n)=\sum_{d|n} 1$ is the number of dividers of n. Dividers of $m^n$ are $1,m,m^2,...,m^n$ then we have that $τ(m^n)=n+1$. Is this correct so far? Now we must prove that $τ(m^n)$ and ...
Could you please help me to understand the mathematics behind MIPS rating formula? The performance of a CPU (processor) can be measured in MIPS. The formula for MIPS is: $$MIPS = \frac{Instruction \ ... 1answer 15 views ### Can the min/max value of a quotient be calculated for a simple division? If I have a simple division x \over y I can rewrite it as x = Qy +R, (where Q is the Quotient and R is the remainder). I know that |y| > R \ge 0. Is there a similar rule for the quotient? 4answers 78 views ### If the 81 digit number 111\cdots 1 is divided by 729, the remainder is? If the 81 digit number 111\cdots 1 is divided by 729, the remainder is? 729=9^3 For any number to be divisible by 9, the sum of the digits have to be divisible by 9. The given number ... 2answers 29 views ### Divisibility (algebra, number theory). Suppose you have$$a b c = ma|yb|yc|y$$Does that imply that$$m|yam_1 = ybm_2 = ycm_3 = ymm_1 m_2 m_3 = y^3$$?? 3answers 98 views ### Probability that 2^a+3^b+5^c is divisible by 4 If a,b,c\in{1,2,3,4,5}, find the probability that 2^a+3^b+5^c is divisible by 4. For a number to be divisible by 4, the last two digits have to be divisible by 4 5^c= \_~\_25 if ... 4answers 55 views ### If a\mid b^2, b^2\mid a^3,\ldots ,a^n\mid b^{n+1},b^{n+1}\mid a^{n+2},\ldots then a=b [duplicate] I'm stuck with this problem : Let a,b positive integers such that$$a\mid b^2, b^2\mid a^3,\ldots ,a^n\mid b^{n+1},b^{n+1}\mid a^{n+2},\ldots$$Show that a=b. If were  b > a  then \lim_{n ... 0answers 37 views ### \exists\ n \gt 34131 with more than 7 odd divisors d_i \gt 1 such as when d_i+1 are accumulated in increasing order to 1 the sums are prime? In the same style as a previous test, I did a little test today looking for all the numbers such as the odd divisors, ordered in increasing order excluding 1, when they are accumulated one by one to ... 0answers 133 views ### Prove that (a-b)^n\mid (a^n-b^n) \iff n=1 under given conditions Suppose that a,b,(a-b) are pairwise co-prime (i.e. a\perp b\perp (a-b)\perp a), and that \frac{a}{2}<b<a, where a and b are both positive integers greater than 2. Let n be odd. ... 2answers 38 views ### Without using prime factorization, show if m\mid n^2 then \gcd(m,n^2/m)\mid n It's easy to use prime factorization to show: If m\mid n^2 then \gcd(m,n^2/m)\mid n. Can anybody find some other proof - perhaps a simple reduction of some sort? Maybe solving m^2x + ... 3answers 60 views ### If n is positive integer, prove that the prime factorization of 2^{2n}\times 3^n - 1 contains 11 as one of the prime factors I have: 2^{2n} \cdot 3^{n} - 1 = (2^2 \cdot 3)^n - 1 = 12^n - 1. I know every positive integer is a product of primes, so that,$$12^n - 1 = p_1 \cdot p_2 \cdot \dots \cdot p_r. $$Also, any idea ... 3answers 56 views ### Problem on factorials and divisiblity of number theory [closed] How do I prove that a!b! completely divides (a+b)! 3answers 969 views ### Proof by induction that n^3 + (n + 1)^3 + (n + 2)^3 is a multiple of 9. Please mark/grade. What do you think about my first induction proof? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof First, introducing a predicate ... 0answers 44 views ### If a^n+n^b\mid c^n+n^d for every n then c=a^k and d=kb . I made a generalization of the following problem (it's a problem from the IMO shortlist in some year) : Let a,b be fixed positive integers . If :$$a^n+n \mid b^n+n$$for every positive integer ... 1answer 53 views ### Separating numbers prime with n in fixed length intervals . This question ( Proving for n \ge 25, p_n > 3.75n where p_n is the nth prime. ) led me to ask the following . Take n>2 a positive integer . Let a_1,a_2,\ldots,a_{\phi(n)} be all ... 1answer 46 views ### Prove that (\frac{-2}{p})= 1 if and only if p is of the form 8k + 1 or 8k + 3 Let p be a prime number. Prove that (\frac{-2}{p})= 1 if and only if p is of the form 8k + 1 or 8k + 3, and then from there conclude that there are infinitely many primes of the form 8k + 3 ... 3answers 432 views ### Why does Wolfram Alpha say that n/0 is complex infinity? I typed a number divided by 0 on Wolfram Alpha and thought that it would say "undefined". However, when I pressed enter it told me that the answer is complex infinity. I have always been taught ... 3answers 105 views ### Dilemma about the value of \frac{4- 4}{4 - 4} I can't find where the mistake is here. Can someone explain how it is possible? 4answers 109 views ### Prove: \forall n\in \mathbb N, (2^n)! is divisible by 2^{(2^n)-1} and is not divisible by 2^{2^n} I assume induction must be used, but I'm having trouble thinking on how to use it when dealing with divisibility when there's no clear, useful way of factorizing the numbers. 5answers 9k views ### Prove that \gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1 For all a, m, n \in \mathbb{Z}^+,$$\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$$5answers 821 views ### Prove n\mid \phi(2^n-1) If 2^p-1 is a prime, (thus p is a prime, too) then p\mid 2^p-2=\phi(2^p-1). But I find n\mid \phi(2^n-1) is always hold, no matter what n is. Such as 4\mid \phi(2^4-1)=8. If we denote ... 2answers 196 views ### n\mid \phi(a^{n}-1) for any a>n? I saw the proof which goes as follows: a^{n} \equiv 1 \pmod{a^{n}-1} , and n is the smallest power of a such that this is true. We also know that by Euler's Identity a^{\phi(a^{n}-1)}\equiv ... 3answers 160 views ### Can exist an even number greater than 36 with more even divisors than 36, all of them being a prime-1? I did a little test today looking for all the numbers such as their even divisors are exactly all of them a prime number minus 1, to verify possible properties of them. These are the first terms, it ... 3answers 823 views ### How to prove that z\gcd(a,b)=\gcd(za,zb) I need to prove that z\gcd(a,b)=\gcd(za,zb). I tried a lot, for example, looking at set of common divisors of the two sides, but I can't conclude anything from that. Can you please give me ... 0answers 122 views ### Suppose that n > 1. Prove that n divides  φ (2^n - 1)  . [duplicate] Suppose that n > 1. Prove that n divides  φ(2^n - 1)  . Hint: Show that 2 has order n mod  2^n - 1  1answer 25 views ### Relation of divisibility - hasse diagram A = \{3,4,5,10,15,20,30,60\} Relation R: \forall x,y \in A : (x,y) \in R \Leftrightarrow y \mid x  Here is my Hasse diagram Is my Hasse diagram drawn correctly? 0answers 58 views ### Smallest n-digit number x with cyclic permutations multiples of 1989 Suppose x=a_1...a_n, where a_1...a_n are the digits in decimal of x and x is a positive integer. We define x_1=x, x_2=a_na_1...a_{n-1}, and so on until x_n=a_2...a_na_1. Find the ... 1answer 34 views ### Working with divisors [closed] Compute ∅ (40), 𝜎(124), 𝑑(124) and check the equality in Σ∅(𝑑) = 40. Here's what I've done so far: Not really sure about the summation equality. ∅ (40) = ∅ ... 3answers 83 views ### Numbers with more than n divisors [duplicate] Numbers with more than 4 divisors = multiples of numbers with exactly 4 divisors. This only applies to 4 (and 2, of course): e.g. numbers with more than 3 divisors != multiples of numbers with ... 3answers 410 views ### Prove that n divides \phi(a^n -1) where a, n are positive integer without using concepts of abstract algebra I need to show that n divides \phi(a^n -1) where a, n are positive integer without using concepts of abstract algebra I know that$$a^n\equiv 1\pmod {a^n-1}$$How do I proceed from there? 0answers 38 views ### Prove that \phi (2^n-1) is a multiple of n for any n>1 [duplicate] Prove that \phi (2^n-1) is a multiple of n for any n>1. I'm not really sure how to start this proof. 1answer 118 views ### Prove that n\mid \phi(a^n-b^n) In this post, I asked how to prove n\mid \phi(2^n-1),(n\in \mathbb N). @Amr and @Abhra Abir Kundu proved more: they proved that n\mid \phi(a^n-1),(a,n\in \mathbb N). The method is very nice. I ... 9answers 1k views ### prove for all n\geq 0 that 3 \mid n^3+6n^2+11n+6 I'm having some trouble with this question and can't really get how to prove this.. I have to prove n^3+6n^2+11n+6 is divisible by 3 for all n \geq 0. I have tried doing \dfrac{m}{3}=n and ... 3answers 108 views ### Prove by induction \vphantom{\Large A}3\mid\left(n^{3} - n\right) So I'm just studying for my midterm and I came across this exercise: Prove by mathematical induction that \vphantom{\Large A}3\mid\left(n^{3} - n\right) for every positive integer n. What ... 3answers 103 views ### Prove by induction that 3\mid n^3 - n Prove by induction that 3\mid n^3 - n. I'm having an argument with my professor whether my exam was right or not. Before I sign a formal complain to get a review on my exam, I'd like to be sure ... 3answers 23 views ### Brett has £135, Dustin has £70, Greg has £35. Brett gives some money to Dustin & Greg. The ratio of the amount of money Brett, Dustin and Greg have now is 3:2:1 How much money did Brett give to Dustin? I considered saying Brett gets 3 parts ... 2answers 259 views ### Verify If Sum of Factorials is Divisible by Integer I am working on preparing for JEE and was working on this math problem. We have the sum,$$\sum_{n=1}^{120}n!=1!+2!+3!+\ldots+120!$$Now I am given the question, which says that what happens when ... 4answers 451 views ### Divisibility by 7. Let b = a_5a_4a_3a_2a_1a_0 integer that has a maximum of six digits. Here we have: if b is a five-digit number, then a_5 = 0; if b is a four-digit number , then a_5, a_4 = 0, and so on. ... 5answers 234 views ### mathematical induction for divisibility: Is this one a valid proof? If so why? I must prove that 7^n-1 (n \in \mathbb{N}) is divisible by 6. My "inductive step" is as follows: 7^{n+1}-1 = 7\times 7^n-1 = (6+1)\times 7^n-1 = 6\times 7^n+7^n-1 So now, 6\times7^n is ... 4answers 169 views ### Divisibility test by 7 Pohlmann-Mass method Step A: If the integer is 1,000 or less, subtract twice the last digit from the number formed by the remaining digits. If the result is a multiple of seven, then so is the ... 6answers 6k views ### How can I prove that n^7 - n is divisible by 42 for any integer n? I can see that this works for any integer n, but I can't figure out why this works, or why the number 42 has this property. 1answer 28 views ### Obscure understanding of Euclid lemma Euclid lemma says "If p is a prime that divides ab, then p divides a or p divides b. If we suppose that p does not divides a, then this implies there are integers s and t such ... 4answers 59 views ### Prove for every odd integer a that (a^2 + 3)(a^2 + 7) = 32b for some integer b. I've gotten this far: a is odd, so a = 2k + 1 for some integer k. Then (a^2 + 3).(a^2 + 7) = [(2k + 1)^2 + 3] [(2k + 1)^2 + 7] = (4k^2 + 4k + 4) (4k^2 + 4k + 8)  =16k^4 + 16k^3 + ... 1answer 59 views ### Is my proof valid for 9 dividing sum of three consecutive cubes? I am trying to use induction. Have I applied it correctly / rigorously enough? Prove that the sum of three consecutive cubes are divisible by 9. Base case: Let n=0. Then 0^3 + 1^3 + 2^3 \equiv ... 1answer 39 views ### Proof. Divisibility number theory Prove that no cancellation is possible for$$\frac{a_1 + a_2}{b_1 + b_2} if $a_1 b_2-a_2 b_1=\pm 1$. I'm new at number theory so if you can be simple it would be great. Here is what I ...
Let $S$ be the smallest set of positive integers satisfying the following conditions: $1 \in S$, If $n \in S$ then $2n \in S$, If $n \in S$ then the digit reversal of $n$ is also in $S$. We assume ...