What is Divisibility: Definition and 170 Discussions

In mathematics, a divisor of an integer



n


{\displaystyle n}
, also called a factor of



n


{\displaystyle n}
, is an integer



m


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



n


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



n


{\displaystyle n}
is a multiple of



m
.


{\displaystyle m.}
An integer



n


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



m


{\displaystyle m}
if



m


{\displaystyle m}
is a divisor of



n


{\displaystyle n}
; this implies dividing



n


{\displaystyle n}
by



m


{\displaystyle m}
leaves no remainder.

View More On Wikipedia.org
  1. E

    Divisibility rules using sum of digits

    I saw someone discussing divisibility rules in another thread and would thought I would make a note that the divisibility rule of 9 of summing the digits to see if you end up with 9 is really a trick of the counting base you are using (base 10). In general, this divisibility rule applies to...
  2. A

    Is a^2 - b^2 divisible by 8 when a and b are odd integers?

    Homework Statement if a and b are odd integer, then 8 l (a2-b2) Homework Equations n/a The Attempt at a Solution if a=b, clearly, 8 l (a2-b2) if not, now, I'm not sure how to continue should i varies b, and make a fixed, then varies a, and make b fixed, is that really the...
  3. H

    How Many Numbers Between 250 and 380 Are Multiples of Both 2 and 7?

    In a set of integers from 250 to 380, inclusive, how many are multiples of both 2 and 7? Please tell me if I'm correct: floor((380-250+1)/(7*2)) = 9 And in general is it always the floor of [cardinality]/[LCM]?
  4. A

    Proving Divisibility Property for Odd Integers: 24 l a(a2-1)

    Homework Statement prove the following if a is an odd integer, then, 24 l a(a2-1) (i'm not familiar with modulo yet, i think it can help, but let don't use it yet ;P) Homework Equations n/a The Attempt at a Solution i stumbled when using 2n+1=a for all integer n, because i will only get...
  5. A

    How to Prove the Divisibility Property Theorem?

    Homework Statement proof the theorem if a l b and b l a then a=+-b Homework Equations The Attempt at a Solution there exist integer p,q such that ap=b and bq=a, then I've no idea how i can relate it to a=+-b.. clue please T_T
  6. R

    Complicated divisibility problem

    Homework Statement If 5 divides m^2 + n^2 + p^2 , prove that 5 divides wither m, or n, or p. Homework Equations m,n,p are all integers The Attempt at a Solution I am having some major problems with this chapter on modular arithmetic. any help is much appreciated! modular arithmetic is...
  7. R

    Divisibility by 11 for all palindromes with an even number of digits

    Homework Statement Prove that every palindromic integer N in base 10 with an even number of digits is divisible by 11. Then prove that every palindromic integer in base k with an even number of digits is divisible by k+1. Homework Equations palindromic means the number reads the...
  8. M

    Divisibility of Mersenne numbers?

    Homework Statement Let M_n= 2^(n) - 1 be the n-th Mersenne number. a) Show that, if m|n, then M_m|M_n b) Show that, if m<n and m does not divide n, then GCD(M_n,M_m) = GCD(M_m,M_r) where r is the remainder of n upon division by m c) Let m,n be arbitrary natural numbers, and let d =...
  9. K

    Two successive digits and divisibility puzzle

    Determine all possible value(s) of a 8-digit base 10 positive integer having the form ABCDEFGH, where each of the capital letters denotes a different digit from 1 to 9, that satisfy each of the following conditions: (I) AB is divisible by 2, and: (II) BC is divisible by 6, and: (III) CD...
  10. K

    Is there a test for binary numbers divisible by 2^n - 1?

    Dear All, I have to test if a binary number is divisible to 2^n - 1 where n is even. Is there a test available for binary numbers like to test a divisibility by 3. Thanks in advance...
  11. J

    Number Theory divisibility proof

    Homework Statement Prove that for any n \in Z+, the integer (n(n+1)(n+2) + 21) is divisible by 3 Homework Equations A previously proved lemma (see below) The Attempt at a Solution I sort of just need a nudge here. I have a previously proven lemma which states: If d|a and d|b...
  12. K

    Proof on the divisibility of integers

    Homework Statement Let a,b be integers where a doesn't =0. Prove that if a divides b, and b divides a, then a=b or a=-bThe Attempt at a Solution I started out with b=aj and a=bk, where j,k are integers. Don't quite know how to proceed
  13. J

    Pythagorean Primes and Gaussian Primes, divisibility question

    Here is an interesting problem that I've been thinking about for a while: Let p be a prime s.t. p = 4m+1 for some integer m. Show that p divides n^2 + 1, where n = (2m)! It comes from a section on principal ideal domains and unique factorization domains. It is well-known that p is the...
  14. M

    Is binary divisibility by 3 determined by even and odd bit count?

    Well i found this sentence: "If the number of even bits minus the number of odd bits is a multiple of 3 (e.g. -3,0,3,6, etc) then the number is divisible by three." Can anyone tell me the proof of this? Thanks
  15. A

    Proving Divisibility: How to Show b|a When b3|a2 - Helpful Tips"

    Hello, If we are given that b3|a2, how do we show that b|a? I started off looking at prime factorizations, but I could use a push in a more substantial direction.
  16. T

    Divisibility of powers of primes

    Hi all, so I was looking at Legendre symbols, and I saw that \left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}. How does one show that \frac{p^2-1}{8} is always an integer? That is, how can we show that 8 | p^2-1? Can a similar method be applied to show that 24 | p^3-p? Thanks :-)...
  17. D

    Divisibility problem with prime numbers

    Homework Statement Let's take a prime number p not equal to 5. Now let's take three integers a,b,c. Prove that if p | (a + b + c) \wedge p | (a^5 + b^5 + c^5), then p | (a^2 + b^2 + c^2) \vee p | (a^3 + b^3 + c^3) Homework Equations I think: (a + b + c)^2 = a^2 + b^2 + c^2 +...
  18. K

    Divisibility of a prime

    if p is any prime other than 2 or 5, prove that p divides infinitely many of the integers 9, 99, 999, 9999, ... If p is any prime other than 2 or 5, prove that p divides infinitely many of the integers 1, 11, 111, 1111, ... Is there a way to do this problem using modular arithmetic? Thanks
  19. H

    Divisibility of Polynomials: Finding the Remainder

    Homework Statement A polynomial p(x) leaves the rest 3 when divided by (x+2) and the rest 8 when divided by (x-6). What's the rest r(x) when p(x) is divided by (x+2)(x-6)? Homework Equations The Attempt at a Solution I wrote the three equations: p(x)=q1(x+2) + 3 p(x)=q2(x-6) +...
  20. T

    Simple number theory, divisibility

    Can you help me with this problem: if a^2 divides b^2, show that a divides b. This was a homework question that I had a while ago and it was solved by using the fundamental theorem of arithmetic. I instead tried to solve it with proof by contradiction: a^2 divides b^2 implies a divides...
  21. J

    Proving (a^n -b^n) Does Not Divide (a^n + b ^n): Divisibility Question

    How can I show that (a^n -b^n) doesn't divide (a^n + b ^n) for all integers a,b, and n? I have that if (a^n -b^n) did divide (a^n + b ^n), then (a^n +b^n) = q (a^n -b^n) which implies b^n = -q*b^n (mod a^n). Then 1 = -q (mod a^n), meaning gcd(b, a^n) = 1. I am unsure of what more I can...
  22. H

    Composite numbers and divisibility (2 problems)

    First of all, I hope this problem is supposed to be here - I'm Swedish and in Sweden "calculus" & "precalculus" are rather odd terms. Anyway..Homework Statement Prove that n3 - n is divisible by 6 if n is a natural number, and divisible by 24 if n is an odd natural number.Homework Equations The...
  23. A

    What is the proof for divisibility of prime numbers?

    Homework Statement a, b, P, and any other numbers introduced are members of the integer set. If P is known to be a prime number, and ab can be divided by P, then prove that either a or b can be divided by P. Homework Equations All properties of real numbers. Need not be explicitly...
  24. K

    A problem of charateristic polynomials' divisibility

    Homework Statement A is a square matrix of size n, B is of size m, C is an m*n(typo,should be n*m) matrix and n>m ,Rank(C)=m. if AC=CB, prove characteristic polynomial of B divides that of A. Homework Equations nothingThe Attempt at a Solution I think I need to prove any eigenvalue of B is an...
  25. K

    8-digit number and divisibility puzzle

    P is a 8-digit base ten positive integer having the form ABCDEFGH that uses each of the nonzero digits from 1 to 8 exactly once, and satisfies all of these conditions: (i) AB is divisible by 8. (ii) BC is divisible by 7. (iii) CD is divisible by 6. (iv) DE is divisible by 5. (v) EF is...
  26. C

    Proving Prime Divisibility of \binom{p}{k}

    \binom{n+1}{k+1}=\binom{n}{k}+\binom{n}{k+1} I'm not sure how to prove this. However...does this work: If p is a positive prime number and 0<k<p, prove p divides \binom{p}{k} Can't I just say that if that binomial is prime, this means that it is only divisible by p and 1 (since...
  27. A

    Question about primes and divisibility abstract algebra/number theory

    Can someone please tell me how to go about answering a question like this? I've been racking my brain for a long time and still don't have a clue...I guess because my background in algebra/number theory really isn't that strong. "What is the greatest integer that divides p^4 - 1 for every...
  28. E

    Divisibility Proof (Abstract Algebra)

    Homework Statement let a belong to N and x,r belong to Z use the definition of divisibility along with the axioms of Integers to prove that IF 5|a and 15|(2ax+r) then 5|r Homework Equations How do I continue the proof?? The Attempt at a Solution So I have: let a belong to N and...
  29. S

    Divisibility & congruences

    which elements of Z/60 are invertible?? what are their inverses? do we have any quick way to do this kind of question??
  30. kreil

    Divisibility Question: Proving 12|(n^2-1) for Odd n^2 and Non-Divisibility by 3

    Homework Statement Suppose that n^2 is odd and that 3 does not divide n^2. Show that 12|(n^2-1) Homework Equations none The Attempt at a Solution Well I know that since n^2 is odd, n^2-1 is even. I'm not sure what the next step would be.
  31. F

    Number Theory - divisibility and primes

    Homework Statement Prove that any integer n >= 2 such that n divides (n-1)! + 1 is prime. Homework Equations The Attempt at a Solution I'm having trouble getting started, I have no idea how to approach this, can someone give a hint on where to begin maybe because I'm just not...
  32. G

    Does divisibility apply to imaginary numbers?

    For example, is 5i "divisible" by 5? Or does divisibility only apply to integers? On that note, is 5pi divisible by 5? Is 5/6 not divisible by 5? Thanks in advance! =)
  33. V

    Divisibility and Congruence problem

    I was trying to work out whether or not 2n+3 divides (2n+1)! for positive integers n. After trying a few cases I think it does not work but I don't know how a proof for this would work. I tried induction but it got really messy. I also tried rephrasing it, such as putting it into modular...
  34. M

    Divisibility Problem: Fast Algorithm for Large Integers A and B

    given two integers A and B that are very big is there any 'fast' algorithm to calculate the remainder of the division \frac{A}{B} or in other similar words to say if B divides or not A thanks.
  35. K

    Trisectible angles | divisibility

    1) We know that if \theta is trisectible (with straightedge and compass), then \theta/3 is constructible. But is it also true that if \theta/3 is constructible, then \theta is trisectible (with straightedge and compass)? If so, then I can say that since 15o is constructible, we have that...
  36. G

    Proving Divisibility of n^3-n by 6

    Homework Statement Prove that n^3 - n is divisible by 6, when n is a nonnegative integer. The Attempt at a Solution Mathematical induction: It works for n=0 It works for n=1 (Extra step, just in case) Check if it works for the (k+1)th step. For it to work, it must be expressible...
  37. M

    Divisibility by 11: Proving the Alternating Sum Method

    Homework Statement what is the test to to see if a number is divisible by 11 and prove it. The Attempt at a Solution If the alternating sum of a numbers digits is divisble by 11 then so is the number. I don't know how to prove it tho.
  38. E

    Finding Largest N for n^5-5n^3+4n Divisibility

    [SOLVED] larson 3.3.19b Homework Statement What is the largest number N for which you can say that n^5-5n^3+4n is divisible by N for every positive integer N. EDIT: change the last N to n Homework Equations The Attempt at a Solution I have just been plugging in things for n and seeing what...
  39. E

    Proving Divisibility of m by 24

    Homework Statement Prove that if n^2+m and n^2-m are perfect squares, then m is divisible by 24.Homework Equations The Attempt at a Solution I found all of the squares mod 24. They are:{0,1,4,9,12,16}. We want to show that if we take anyone of these as n^2, then n^2+m and n^2-m cannot be in...
  40. E

    Induction Proof for Divisibility

    [SOLVED] induction proof Homework Statement Given a set of n+1 integers between 1 and 2n (inclusive), show that at least one member of the set must divide another member of the set. Use induction. Homework Equations The Attempt at a Solution When n=1, this is obvious. Assume the result is...
  41. S

    Proof of Divisibility of 8 rule

    Homework Statement Let n be a natural number. If the number formed by the last three digits of n is divisible by 8, then n is divisible by 8. Homework Equations Natural numbers are the set of {1,2,3,4,5,6,...} The Attempt at a Solution I believe we should use a direct proof to...
  42. P

    Proof: integers divisibility property

    Someone please help me with this qiestion: Prove that for all integers a, b, and c, if a divides b but not c then a does not divide b + c, but the converse is false. Thanks.
  43. P

    Is Every Integer in the Decimal System Divisible by 5?

    I need some help proving this statement. Prove that a positive integer is divisible by 5 if and only if it's last digit is either 0 or 5. Thanks
  44. T

    Sums of natural numbers to p and subsequent divisibility

    So I'm taking an introductory number theory course as an undergraduate, and this particular "genre" of questions really just has me stumped. Pick a prime p such that p is odd. Now, take various sums up of natural numbers from 1 to p, and show that the results are divisible by p. For...
  45. T

    Prime numbers and divisibility

    Find all prime numbers (p,q,r), that numbers pq+pr+rq and p^3+q^3+r^3-2pqr are divided by p+q+r
  46. T

    Exploring Divisibility Patterns in a Recurrent Integer Sequence

    We have recurrent sequence of integer number a_{1},a_{2},... a1=1, a2=2 a_{n}=3a_{n-1}+5a_{n-2} for n=3,4,5,... Is integer number k>=2, that (a_{k+1}*a_{k+2}) mod a_{k} = 0 ? Please for quick help :)
  47. K

    Can a Sequence of 1's and 0's Be a Multiple of Any Integer?

    Show that for any n>1 we can construct a positive integer consisting of only 1's and 0's such that this integer is a multiple of n.
  48. K

    Mathmatical Induction Problem (Divisibility)

    Homework Statement Use Mathematical Induction to prove that 12^n + 2(5^{n-1}) is divisible by 7 for all n \in Z^+ Homework Equations The Attempt at a Solution First, show that it works for n = 1: 12^1 + 2 \cdot 5^0 = 14 , 14/7 = 2 Next assume: 12^k + 2(5^{k-1}) = 7A Then, prove for...
  49. R

    Odd or Even? Exploring 0's Divisibility

    Is 0 an odd or even number? The reason why I ask is this: I need to write cosh(x) as the sum of an even and odd function. I could only come up with cosh(x) = cosh(x) + 0, where cosh(x) would be the even and 0odd. However, this doesn't make any sense since 0 is exactly divisible by 2 with no...
  50. L

    Divisibility and p's and q's

    If 3p^2 = q^2 and p and q are integers, how do I prove that 3 is a common divisor for p and q? My attempt: q^2 is divisible by 3, so q is divisible by 3. I can't prove that p is divisible by 3.
Back
Top