Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [divisibility]

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

If $a$ and $b$ are integers, $a$ divides $b$ if $b=ca$ for some integer $c$. This is denoted $a\mid b$. It is usually studied in introductory courses in number theory, so add if appropriate.

A common notation used for the phrase "$a$ divides $b$" is $a|b$. It is also common to negate the notation by adding a slash like this: "$c$ does not divide $d$" written as $c\nmid d$. Note that the order is important: for example, $2|4$ but "$4\nmid 2$".

This notion can be generalized to any ring. The definition is the same: For two elements $a$ and $b$ of a commutative ring $R$, $a$ divides $b$ if $ac=b$ for some $c$ in $R$.

Divisibility in commutative rings corresponds exactly to containment the poset of principal ideals. That is, $a$ divides $b$ if and only if $aR\subseteq bR$. For commutative rings like principal ideal rings, this means that divisibility mirrors exactly the poset of all ideals of the ring.

The topics appropriate for this tag include, for example:

  • Questions about the relation $\mid$.
  • Questions about the GCD and LCM.

There are divisibility rule that is a shorthand way of determining whether a given integer is divisible by a fixed divisor without performing the division, usually by examining its digits.

6170 questions
1
vote
4 answers

Problem on gcd of two numbers

Let $(a,b)$ be the Greatest Common Divisor of two numbers $a$ and $b$. Then, if $(r,n)=1$, is it true that $(r,n-r)=1$? If correct, prove it. Thanks in advance :)
hanugm
  • 2,353
  • 1
  • 13
  • 34
1
vote
1 answer

Divisibility problem: $ \frac{3^{m}}{2^{n} - 3^r} $

Is divisible a power of 3 for a difference of powers of 2 and 3? That is, can result, this division, in an integer? $$ \frac{3^{m}}{2^{n} - 3^r} $$ where $n,m,r$ natural number. Edit: $n>r$, $r=m+1$.
Lely
  • 1,057
1
vote
3 answers

Divisibility proof problem

I need assistance with the following proof. Let a,b,c,m be integers, with m $\geq$ 1. Let d = (a,m). Prove that m divides ab-ac if and only if $\frac md $ divides b-c. Alright, I know that since d = (a,m) there exists an r and t such that $ar + mt…
Benji_Bombadill
  • 341
1
vote
1 answer

prove that if $u$ is an integer which divides all integers, then $u$ is the unity

prove that if $u$ is an integer which divides all integers, then $u$ is the unity this is a divisibility exercise, i dont know how to use the definition of divisibility* and the definition of unity** *$a\mid b \implies \exists c\in \mathbb Z$, such…
Victor F Salazar G
  • 1,297
1
vote
2 answers

GCD and EEA Proof

Let n be an arbitrary positive integer. Express $\gcd(8n + 3, 5n - 2)$ as a function of $n$. Is the answer so trivial that all you need to do it multiply it out using EEA? So would $f(n) = (8n+3)x + (5n - 2)y$ work?
user242743
  • 175
  • 3
  • 6
1
vote
2 answers

Why does p|4q also mean p|q if p is odd?

Why does p|4q also mean p|q if p is odd? It might be a simple question but it's in the answers and I want to know.
Daniel Valentine
  • 71
1
vote
1 answer

Given a, b are integers. Show that GCD(a,b) = GCD(b,a).

Where do I start? I don't really understand what the difference is between the two. It seems so logic to me that I don't know how wich parts I should explain. How to start, What is there to be shown?
logicjohnnny
  • 39
1
vote
1 answer

finding unknowns and proof

The procedures for using cutting-adding method for testing a number M to be a multiple of 59 are as follows: 1 cut the units digit of M 2 add the remaining integer by r times of the deleted digit. 3 go to step 1 until the resulting integer is a…
Tessa
  • 41
1
vote
3 answers

Divisibility of a prime number

I need help with the following: Show that: If $p$ is prime such that $p$ divides $a^n$ Then $p^n$ divides $a^n$ I know that if $p$ is a prime and divides a square number $a$ then $p$ also divides $a$ but I'm not sure how to apply this to the given…
Benji_Bombadill
  • 341
1
vote
3 answers

Prove $\operatorname{gcd}(a-1,a+1)$

Let $a$ be an integer. After looking at several examples, make a conjecture about the value of $\operatorname{gcd}(a-1,a+1)$ and prove it. Ok. I found that: if $a$ is even, $\operatorname{gcd}(a-1,a+1)=1$; if $a$ is odd,…
Wes
  • 497
1
vote
3 answers

For every integer $a$, if $a \not\equiv 0\pmod3$, then, $a^2\equiv 1\pmod3$.

It is always confusing to prove with $\not\equiv$. Should I try contrapositive?
Wes
  • 497
1
vote
1 answer

Proof verification on Fermat's Little Theorem exercise - new way to solve problem?

I don't know if I'm correct, since I didn't even have to use the hint. So I'm asking for proof verification since I am also not too confident on primes. Suppose $\gcd(a, 35) = 1.$ Show that $a^{12} - 1$ is divisible by $35$. Here's the hint that…
Don Larynx
  • 4,703
1
vote
1 answer

divisibility of integral part of a surd

Given that "$n$" belongs to prime numbers and is greater than 2 ; $(a,b)$ belongs to integers and $0<\sqrt{a}-b<1$ $(\sqrt{a}+b)^n=N+f$ where $f \in (0,1)$ Show that $N$-$2b^n$ is divisible by $2abn$
Tom Lynd
  • 1,342
1
vote
1 answer

Prove that if $d$ is a divisor of $a$ and $b$ then $d$ is a divisor of $2020$, I think the book is wrong

$a = 113n + 10$ $b = 89n - 10$ $n$ is a natural number Question: Prove that if $d$ is a divisor of $a$ and $b$ then $d$ is a divisor of $2020$ The book's solution: $d / a$ $d / b$ then $d / a + b$ so $d / 202n$ $d / 10(202n)$ $d / 2020n$ so $d /…
TechnoKnight
  • 433
1
vote
2 answers

Proof of the divisibility rule of 11.

We know, A number is divisible by $11$ if the difference of the sum of the digits in the odd places and the sum of the digits in the even places is divisible by $11$. For example, Let's consider $814$: Sum of the digits in the odd places $= 8 + 4…
Nur Mohammed Mehedy Hassan
  • 11
  • 1
  • 2
1 2 3
…
30 31