What is Divisibility: Definition and 170 Discussions

In mathematics, a divisor of an integer


{\displaystyle n}
, also called a factor of


{\displaystyle n}
, is an integer


{\displaystyle m}
that may be multiplied by some integer to produce


{\displaystyle n}
. In this case, one also says that


{\displaystyle n}
is a multiple of


{\displaystyle m.}
An integer


{\displaystyle n}
is divisible or evenly divisible by another integer


{\displaystyle m}


{\displaystyle m}
is a divisor of


{\displaystyle n}
; this implies dividing


{\displaystyle n}


{\displaystyle m}
leaves no remainder.

View More On Wikipedia.org
  1. M

    B Relation between Division and multiplication

    For example what is ##\frac {169}{13} = ?## This says “When ##169## is divided into ##13## groups how many there are in each group?” This can be converted into a multiplication problem like this “##13## groups of how many in each group makes ##169##?” This is ##13 * ? = 169##. It can be solved...
  2. Rikudo

    A problem related to divisibility

    So, ##n\, |\, (p − 1)## implies ##p = nk + 1## and ##p ≥ n + 1##. Clearly, ## p \,|\, n^3 − 1## implies either : ##p \,|\, n − 1 ## (which is impossible, because p cannot be less than ##n-1##) or ##p \,|\,n^2 + n + 1##. Now, our main focus is ##p\, |\,n^2 + n + 1##. Since ##p = nk + 1##...
  3. Z

    Divisibility Test: Determine if a Number is Divisible by 6, 8, 4

    Mod note: Moved from technical forum section, so missing the usual sections. Hi am 16yo and i was unable to tackle this quiz even despite trying some online calculators. i hope someone can explain to me step by step. thanks In each of the following numbers without doing actual division...
  4. M

    Proof: Divisibility of Integers by 4

    Proof: Let ## N ## be an integer. Then ## N=a_{m}10^{m}+a_{m-1}10^{m-1}+\dotsb +a_{1}10+a_{0} ## for ## 0\leq a_{k}\leq 9 ##. Note that ## 10^{k}\equiv 0\pmod {4} ## for ## k\geq 2 ##. Thus ## 4\mid N\Leftrightarrow N\equiv 0\pmod {4}\Leftrightarrow a_{1}10+a_{0}\equiv 0\pmod {4} ##...
  5. M

    Proof: Integer Divisibility by 3 via Polynomials

    Proof: Let ## P(x)= \Sigma^{m}_{k=0} a_{k} x^{k} ## be a polynomial function. Then ## N=a_{m}10^{m}+a_{m-1}10^{m-1}+\dotsb +a_{1}10+a_{0} ## for ## 0\leq a_{k}\leq 9 ##. Since ## 10\equiv 1\pmod {3} ##, it follows that ## P(10)\equiv P(1)\pmod {3} ##. Note that ## N\equiv (a_{m}+a_{m-1}+\dotsb...
  6. M

    Divisibility of Integers ## 176521221 ## & ## 149235678 ## by 9 & 11

    First, consider the integer ## 176521221 ##. Observe that ## 1+7+6+5+2+1+2+2+1=27 ##. Since ## 9\mid (1+7+6+5+2+1+2+2+1) ##, it follows that ## 9\mid 176521221 ##. Note that ## 1-2+2-1+2-5+6-7+1=-3 ##. This means ## 11\nmid (1-2+2-1+2-5+6-7+1) ##. Thus ## 11\nmid 176521221 ##. Therefore, the...
  7. S

    MHB Divisibility of (1!+2!+3!+...+100!)^2 by 5

    1.The remainder when dividing (1!+2!+3!+...+100!)^2 by 5 is? 5 divides evenly into 5!, 6!, 7!, ..., 100!. It would also divide evenly into things like 2!*8! or 20!*83!, but not 4!*3! but whether then ^2 affects the rest? And what is answer?Thanks
  8. Petek

    MHB Proving Divisibility of 5c+9d and 3c+10d by 23

    Let c and d be integers. Suppose that 5c + 9d is divisible by 23. Show that 3c + 10d also is divisible by 23.
  9. anemone

    MHB Prove Divisibility: $(x-y)^2+(y-z)^2+(z-x)^2=xyz$ yields $x^3+y^3+z^3$

    Let $x,\,y,\,z$ be integers such that $(x-y)^2+(y-z)^2+(z-x)^2=xyz$, prove that $x^3+y^3+z^3$ is divisible by $x+y+z+6$.
  10. anemone

    MHB Integers and Divisibility Challenge

    Prove that $\dfrac{378^3+392^3+1053^3}{2579}$ is an integer.
  11. M

    MHB Digit sum rule for the divisibility by 9

    Hey! :o Let $n\in \mathbb{N}$, $2\leq m\in \mathbb{N}$ and $a\in \mathbb{Z}$. I want to show that $a\left (m+1\right )^n \overset{(9)}{\equiv} a$. I have done the following: \begin{equation*}a\left (m+1\right )^n \overset{(9)}{\equiv} a\left (0+1\right )^n \overset{(9)}{\equiv} a\cdot 1^n...
  12. Philip Robotic

    Prime numbers and divisibility by 12

    Homework Statement Prove that if ##p## is a prime number and if ##p>5## then ##p^2-37## is divisible by ##12## Homework EquationsThe Attempt at a Solution So I think that the number ##p^2-37## should be expressed in a way that we can clearly see that it is divisible by 3 and by 2 twice...
  13. Q

    MHB Divisibility Problem: Prove Existence of $i,j$

    $$\text{ Let } n∈N \text{ and } (a1,a2,…,a_{n})∈\mathbb{Z}^{n}. \text{ Prove that always exist } i,j∈ \underline{n} \text{ with } i≤j \text{ so } \sum\limits_{k=i}^{\\j} a_{k} \text{ divisible by n} .$$
  14. R

    B Exploring Divisibility Rules in Mathematics: A Guide for Self-Study

    I've realized that a lot of textbook questions require me to google things because I have no clue how to prove certain things. For example, I do not have the fact that if the last 2 digits in a number are divisible by 4, that number is then divisible by 4. I'm pretty sure my teacher will not...
  15. Jarvis323

    I Divisibility of bounded interval of reals

    Can (0,1)\subset\mathbb{R} be divided into an infinite set S of non-empty disjoint subsets? It seams like any pair of points in different subsets of the partitioning must have a finite difference, and so there must be some smallest finite difference overall, d where |S| \leq 1/d. Can someone...
  16. Terry Coates

    B Divisibility by p^p: A, B, C Sol'ns & More

    I have found how to get three integers A B and C such that A^p - B^p - C^p is of form N*p^p with p > 2 and N not divisible by p+2.or p. This is A = p^(p-1) , B = A-1, C = 1 . This works with p = 3 , 4 and 5. My questions are: does it work with all values of p > 2 and is there any other way...
  17. R

    I Testing Primality of 377 with Divisibility

    Take for example 377 to test its primality. I will only test its divisibility with (3*5*7*...*125) (because 377/3=125.67, so here the multiplication series end with 125 ). 377 will be able to divide it. (Since I know 377=13*29, i.e in the numerator 13 & 29 will be divided by 377, hence...
  18. FallArk

    MHB How to show that the Fibonacci sequence is a divisibility sequence?

    I wanted to prove that the Fibonacci sequence is a divisibility sequence, but I don't even know how to prove it. all I know is that gcd\left({F}_{m},{F}_{n}\right)={F}_{gcd\left(m,n\right)} and I should somehow use the Euclidean algorithm?
  19. lfdahl

    MHB Prove: Is ${2017 \choose 652}$ Divisible by 343?

    Is the binomial coefficient: ${2017 \choose 652 }$ divisible by $343$? Please prove your statement.
  20. J

    What is the proof for n(n^4 - 1) = 10Q for some values Q and n being integers?

    For some values Q and n being integers, prove that n(n^4 - 1) = 10Q. So I've tried this with induction, but it gets pretty messy pretty quickly. So I can see that the LHS will be even no matter what, but I'm not sure where to go beyond this.
  21. Jaroslav

    Prove divisibility, mathematical induction

    I'm still learning English, had to use dictionary and translator, so I'm sorry if its unclear, i will try to explain it more if needed. Homework Statement For n belonging to N when n is even and n > 3, prove that (4^(n-3) + 5^(n-3) + 9) is divisible by 9 Homework Equations 3. The Attempt at...
  22. VMP

    I Problem with recursive sequence, sum and divisibility

    Hello everyone, I have an issue solving the following problem: You're on a mathematical Olympiad, there are m medals and it lasts for n days. First day committee gives U_{1}=1+\frac{1}{7}(m-1) medals. On the second day U_{2}=2+\frac{1}{7}(m-2-U_{1}) medals, and so on... On the last day...
  23. M

    MHB Proving Divisibility of Polynomials in Field Extensions

    Hey! :o Let $K/F$ be a field extension, $f,g\in F[X]$. I want to show that if $g\mid f$ in $K[X]$, then $g\mid f$ also in $F[X]$. Suppose that $g\mid f$ in $K[X]$. Then $f=g\cdot h$, where $h\in K[X]$. We have to show that $h\in F[X]$. Could you give me some hints how we could show that...
  24. T

    Proving Divisibility: Modular Arithmetic and the Pattern of 16^43 - 10^26 Mod 21

    Hi I'm reading a text about modular arithmetic, Prove that 16^43 - 10^26 actually is divisible by 21. They separate it by showing it is divisible by 7 and 3 they showed 16 \equiv 2 \textrm{ mod 7} \\ 16^2 \equiv 2^2 \equiv 4 \textrm{ mod 7} \\ 16 \equiv 2^3 \equiv 1 \textrm{ mod 7} \\ So...
  25. kaliprasad

    MHB Least Possible Value of a+b: 11 & 13 Divisibility

    find the least possible value of a + b where a and b are positive integers and 11 divides $a+ 13b$ and 13 divides $a + 11 b$
  26. S

    Definition of Divisibility

    Question: If x | y, (is true), then x ≤ y and x ≠ 0. For instance, if x > y, then there are no integer solutions to equation kx = y and thus, x does not divide y. Is this a correct proposition?
  27. K

    MHB Divisibility of a polynomial by another polynomial

    I have this question: Find all numbers $n\geq 1$ for which the polynomial $x^{n+1}+x^n+1$ is divisible by $x^2-x+1$. How do I even begin? **So far I have that $x^{n+1}+x^n+1 = x^{n-1}(x^2-x+1)+2x^n-x^{n-1}+1,$ and so the problem is equivalent to finding $n$ such that $2x^n-x^{n-1}+1$ is...
  28. G

    Divisibility Problem: Show That n=3

    Homework Statement Show that the only ##n \in \mathbb{N}-\{0,1\} ## such that ##2n-1|(3n^2-3n+1)(3n^2-3n+2)## is 3. Homework Equations ## P_n = (3n^2-3n+1)(3n^2-3n+2) ## Addition and multiplication in ## \mathbb{Z}/(2n-1)\mathbb{Z} ## The Attempt at a Solution Hello, I'm not 100% sure my...
  29. P

    Proving/Disproving: Int x, y, z Divisibility Claim

    I wasn't sure if this went in math, or computer science. I'm posting it here, because it is for a computer science course, although it's technically mathematical proofs... 1. The problem: Prove or disprove the following claim: For all integers x, y, and z, if x does not divide yz then x does...
  30. Colleen G

    Proof by Induction Involving Divisibility

    Homework Statement Let P(n): 7|(34n+1-52n-1. Prove that P(n) is true for every natural number n. Homework Equations *I know that proving by induction requires a proving P(1) true, and then proving P(k+1) true. *If a|b, then b=a*n, for some n∈ℤ The Attempt at a Solution I have proved the "base...
  31. C

    Show that for each a < b a, b ∈ N we have the following

    1) 3^(2^a) + 1 divides 3^(2^b) -1 2) If d > 2, d ∈ N, then d does not divide both 3^(2^a) + 1 and 3^(2^b) -1 Attempt: Set b = s+a for s ∈ N m = 3^(2^a). Then 3^(2^b) - 1 = 3^[(2^a)(2^s)]-1 = m^(2^s) -1 Thus, m+1 and m-1 divides m^(2^s) -1 by induction. If s = 1, then m^(2^s) -1 = m^2 -...
  32. anemone

    MHB Prove Divisibility of $a^3+b^3+c^3$ Using $(a-b)^2+(b-c)^2+(c-a)^2=abc$

    Let $a,\,b,\,c$ be integers such that $(a-b)^2+(b-c)^2+(c-a)^2=abc$. Prove that $a^3+b^3+c^3$ is divisible by $a+b+c+6$.
  33. B

    MHB Prove: Divisibility & Sums of Distinct Natural Numbers

    Let $a_{1},\dots,a_{n},\,n>2$ distinct natural numbers. Prove that if $p_{1},\dots,p_{r}$ are prime numbers and they divide $a_{1}+\dots+a_{n}$ then exists an integer $k>1$ and a prime $p\neq p_{i},\,\forall i=1,\dots,r$ such that $p\mid a_{1}^{k}+\dots+a_{n}^{k}.$
  34. M

    Binomial Coefficient of a Prime Power

    Homework Statement Let p be a prime, k be positive integer, and m ∈ {1, 2, 3, ..., pk-1}. Without using Lucas' theorem, prove that p divides \binom{p^k}{m}. Homework Equations The definition of the binomial coefficients: \binom{a}{b} = \frac{a!}{b! (a-b)!} The Attempt at a Solution I've...
  35. E

    Binomial expansion- divisibility

    Homework Statement The integer next to (√3 + 1 )^2n is -- (n is a natural number) Ans: Divisible by 2^(n+1) Homework EquationsThe Attempt at a Solution (√3 + 1 )^2n will have an integral and a fractional part. So, I + f = (√3 + 1 )^2n (√3 - 1 )^2n will always be fractional as (√3 - 1) < 1 So...
  36. Greg

    MHB Divisibility problem (number theory, I believe)

    Let $x$ and $y$ be positve integers such that $xy$ divides $x^2+y^2+1$. Show that $$\frac{x^2+y^2+1}{xy}=3$$
  37. B

    MHB Sum of k-powers and divisibility

    Let $a_{1},\dots,a_{n},\, n>2$ positive and distinct integer. Prove that the set of primes divisors of the numbers $$a_{1}^{k}+\dots+a_{n}^{k}$$with $k\in\mathbb{N}$ is infinite.
  38. I

    Proving Divisibility: Solving ##1900^{1990} - 1## with the Power Rule

    Homework Statement Prove that ##1900^{1990} - 1## is divisible by ##1991## Homework Equations ##x^n - 1 = (x - 1)(x^{n-1} + x^{n-2} + ... + 1)## The Attempt at a Solution [/B] Quite naturally the first step I took was to attempt the factorisation and see what that got me: ##1900^{1990} -...
  39. B

    MHB Tests of Divisibility- Simple tricks

    With this simple short cuts you can find out a number is divisible by a given number Divisible by 2: A number is divisible by 2, if its unit’s digit is any of 0, 2, 4, 6, 8. Example: 6798512 Divisible by 3: A number is divisible by 3, if sum of its digits divisible by 3. Example : 123456...
  40. TheSodesa

    A problem concerning divisibility and the number 31. (Number theory)

    Homework Statement Basically, I'm working on a problem where I'm supposed to find a missing digit in a social security number. The number is as follows: 301 X91 - 2005. where X is the missing digit. Now, how these numbers are constructed, is that the first six numbers are the persons...
  41. T

    Implications of the divisibility of time for the study of the big bang

    Does the fact that time is infinitely divisible have implications for studying the big bang? As with all studies of historic events, we are looking at the big bang from a backwards perspective. So, if we look at the first second of the start of our universe in the big bang model, we try to...
  42. 4

    Keeping track of number divisibility

    Hello, I've been wondering if there is any way to keep track of the divisibility tree. For instance, 5+5=10, and 1+4=5 and 2+3=5 hence 1+4+2+3=10. Now hypothetically, I know that '1' occurs at location 2, '4' occurs at location 1, '2' occurs at location 4 and '3' occurs at location 1 and they...
  43. K

    Prove Divisibility: Proving & Disproving

    Homework Statement a.) Prove: If an integer ##a## does not divide ##bc##, then ##a## does not divide ##b## and ##a## does not divide ##c##. b.) State and either prove or disprove the converse of the above statement. The Attempt at a Solution a.) Proof by contrapositive ## a|c \vee a|b...
  44. lfdahl

    MHB Divisibility Challenge: Find Smallest Integer for $f(x)$

    Let $f(x) = 5x^{13}+13x^5+9\cdot a \cdot x$ Find the smallest possible integer, $a$, such that $65$ divides $f(x)$ for every integer $x$.
  45. kaliprasad

    MHB Polynomial Divisibility Problem: Proof & Corollary

    problem For any polynomial P(x) show that P(a) - P(b) is divisible by a-b Proof: Let $p (x) = t_nx^n + t_{n-1} x^{n-1} + \cdots + t_0$ Then $p (a) = t_na^n + t_{n-1} a^{n-1} + \cdots + t_0$ $p (b) = t_nb^n + t_{n-1} b^{n-1} + \cdots + t_0$ So $p (a) – p(b) = t_n(a^n- b^n) +t_{n-1}...
  46. M

    Algebraic proofs of divisibility

    Hello, I have a problem with algebra and divisibility etc. I have a swedish textbook that really sucks. Not a good solutions section and no separate solutions manual either. Just a lot of proofs to show. At the moment I'm stuck at proofs with divisibility. I have two examples: 1)...
  47. EternusVia

    Infinite divisibility of matter?

    Hi all. I'm rather a novice in the realm of physics, aside from a class in high-school and my own independent interest. I often wonder if matter is infinitely divisible. What if it's possible to divide quarks, gluons, etc, we just don't have the methods? Does anyone have input on this...
  48. U

    Complex numbers polynomial divisibility proof

    I'm not sure whether this should go in this forum or another. feel free to move it if needed Homework Statement Suppose that z_0 \in \mathbb{C}. A polynomial P(z) is said to be dvisible by z-z_0 if there is another polynomial Q(z) such that P(z)=(z-z_0)Q(z). Show that for...
  49. M

    Divisibility Proof Writing: Exploring the Cancellation Property in Z

    Homework Statement this is the original question prove: \forall c \in Z, a≠ 0 and b both \in Z$ a|b ⇔ c*a|c*b Then he corrected himself by saying for problem 1: to show that ca | cb implies a | b ... you must assume c NOT = 0 and invoke "Cancellation Property" of Z. This kind...
  50. M

    Discrete proofs involving divisibility

    I'm trying to do some extra course work to prepare for my final next week but I'm having a lot of trouble with the book problems. They talk about a lot of things we weren't taught. Can someone help me out here? Prove: n\niZ, n= a multiple of gcd(a,b) ⇔ n is a linear combination of a and b This...