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

learn more… | top users | synonyms (1)

2
votes
3answers
117 views

How to prove or disprove that $\gcd(ab, c) = \gcd(a, b) \times \gcd(b, c)$?

I'm new to proofs, and am trying to solve this problem from William J. Gilbert's "An Introduction To Mathematical Thinking: Algebra and Number Systems". Specifically, this is from Problem Set 2 ...
1
vote
5answers
147 views

$2730\mid n^{13}-n\;\;\forall n\in\mathbb{N}$

Show that $2730\mid n^{13}-n,\;\;\forall n\in\mathbb{N}$ I tried, $2730=13\cdot5\cdot7\cdot2$ We have $13\mid n^{13}-n$, by Fermat's Little Theorem. We have $2\mid n^{13}-n$, by if $n$ even ...
-1
votes
1answer
53 views

Proof by induction and divisibility $21 | (4^{n+1} + 5^{2n-1}) $ [duplicate]

Prove by induction: $21 | (4^{n+1} + 5^{2n-1}) $ Skipping through the basis and onto the induction: $4\cdot 4^{n+1}+5^2 \cdot 5^{2n-1}=21a $ for some integer $a$ The following steps were: ...
0
votes
1answer
126 views

For natural numbers $a$ and $b$, show that $a \Bbb Z + b \Bbb Z = \gcd(a, b)\Bbb Z $

For natural numbers $a$ and $b$, show that $a \Bbb Z + b \Bbb Z = \gcd(a, b)\Bbb Z $ I just basically said that the gcd of a and b { written as C } obviously divides aZ and bZ, therefore it can be ...
0
votes
2answers
34 views

If u|s and v|t and gcd(s,t) = 1 then gcd(u,v) = 1

Proposition 1. If $\def\divides\mathrel{|}u \divides s$ and $v \divides t$ and $\gcd(s,t) = 1$ then $\gcd(u,v) = 1$. Solution. Assume $u \divides s$ and $v \divides t$. Since $\gcd(u, v) \divides u$, ...
2
votes
1answer
117 views

Proof Without Words for $GCD(a,b) \cdot LCM(a,b)=ab$

Is there any proof without words for the identity $GCD (a,b) \cdot LCM(a,b)=ab$ ?
3
votes
1answer
276 views

Show that if $a$ and $b$ are positive integers then $(a, b) = (a + b, [a, b])$.

Show that if $a$ and $b$ are positive integers then $(a, b)=(a + b, [a, b])$. I was thinking that since $[a, b]=LCM(a, b)=\frac{ab}{(a, b)}$ that if $d= (a + b, [a, b])$, then $d|[a,b]$ and thus ...
0
votes
0answers
43 views

Proof that $ k^2<2^k$ [duplicate]

I'm struggling with this problem of proof by induction: For any natural number $k\geq 5$, prove that $k^2<2^k$. I assumed that $k^2<2^k$ I want to show that $(k+1)^2<2^{k+1}$ The ...
2
votes
6answers
134 views

Proof that $n^3-n$ is a multiple of $3$. [duplicate]

I'm struggling with this problem of proof by induction: For any natural number $n$, prove that $n^3-n$ is a multiple of $3$. I assumed that $k^3-k=3r$ I want to ...
0
votes
2answers
2k views

How many positive integers less than 1000 are divisible [closed]

How many positive integers less than 1000 c) are divisible by both 7 and 11? d) are divisible by either 7 or 11? e) are divisible by exactly one of 7 and 11?
0
votes
2answers
83 views

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 ...
0
votes
5answers
116 views

Proof: $\;n^2\;$ is even if and only if $\;n\;$ is even.

Please help how would you go about doing this? I'm studying for a final. This is on a study guide. I'm having a lot of trouble with this class. Prove that $n^2$ is even if and only if $n$ is even. ...
2
votes
3answers
109 views

Why is it that “If 3 cannot divide ”q“ there will be a remainder of 1 or 2”?

I am studying proofs in discrete math and I ran into this statement that "If 3 cannot divide "q" there will be a remainder of 1 or 2". I know that this is some pretty basic stuff but I am having a ...
0
votes
1answer
24 views

Methodology to solve modulus equation?

I am trying to solve this equation (d*49) % (43480 * 242343) = 1 for the variable d. I was attempting to use the Extended Euclidean algorithm but am not sure ...
3
votes
2answers
38 views

A question on greatest common divisor

I had this question in the Maths Olympiad today. I couldn't solve the part of the greatest common divisor. Please help me understand how to solve it. The question was this: Let $P(x)=x^3+ax^2+b$ and ...
0
votes
1answer
43 views

GCD's and Proofs

Let p and q be odd primes. Prove that gcd(p + q, p - q) = 2. I have considered EEA to multiply it out, but I'm unsure where to go from there.
3
votes
3answers
85 views

Why does $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1$ have new divisors $59$ and $509$ all of a sudden?

I am a noob when it comes to math so please bear with me. Why $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1$ has $2$ new divisors $59$ and $509$. I mean, all of its divisors are prime factors and ...
1
vote
1answer
35 views

Knowing $a|bx$ can we conclude that $\frac{a}{gcd(a,b)}|\frac{bx}{gcd(a,b)}$

Knowing $a|b$ can we conclude that $\frac{a}{gcd(a,b)}|\frac{b}{gcd(a,b)}$? My apologies the thing I was actually looking for was actually if we have $a|bx$ can we conclude that ...
0
votes
1answer
48 views

Is there a logic for recursion rules of divisibility?

I knew the divisibility rule for 7, but my sir told me that these methods are known as recursion rules for divisibility. My sir also told them for 11, 13,17,19. But is there any logic behind it? Or is ...
3
votes
3answers
908 views

$n^2 + 3n +5$ is not divisible by $121$

Question: Show that $n^2 + 3n + 5$ is not divisible by $121$, where $n$ is an integer.
0
votes
3answers
66 views

If $\gcd(a,n) = 1$ and $\gcd(b,n) = 1$, then $\gcd(ab,n) = 1$.

If $\gcd(a,n) = 1$ and $\gcd(b,n) = 1$, then $\gcd(ab,n) = 1$. Also... $a,b$ and $n$ are natural numbers. I feel I should begin with EEA to multiply out the gcd's, but I don't know where to go from ...
1
vote
5answers
140 views

How to show $(mn)!$ divides $(m!)^n$?

How to show $(mn)!$ divides $(m!)^n$, $m$ and $n$ is integers?
1
vote
3answers
350 views

Show that if $n$ is not divisible by $2$ or by $3$, then $n^2-1$ is divisible by $24$.

Show that if $n$ is not divisible by $2$ or by $3$, then $n^2-1$ is divisible by $24$. I thought I would do the following ... As $n$ is not divisible by $2$ and $3$ then ...
-2
votes
2answers
58 views

How many seven digit numbers are there that are divisible by eleven?

How many seven-digit numbers are there that are divisible by 11? In other words, I want to find the number of seven digit numbers that are divisible by 11.
1
vote
2answers
71 views

Show that the matrix is invertible

let $A \in M_n(F)$ be a n by n matrix with values from an unknown field $F$. $P_A(t)$ is the characteristic polynomial of $A$, and $g(t) \in F[t]$ a polynomial of an unknown degree. assume that ...
2
votes
1answer
362 views

Prove by induction that $a-b|a^n-b^n$ [duplicate]

Given $a,b,n \in \mathbb N$, prove that $a-b|a^n-b^n$. I think about induction. The assertion is obviously true for $n=1$. If I assume that assertive is true for a given $k \in \mathbb N$, i.e.: ...
0
votes
1answer
57 views

Is it true that $6|p^2 \implies 6|p$, where $p \in \mathbb{N}$

Is it true that $6|p^2 \implies 6|p$, where $p \in \mathbb{N}$ Where $6|p$ is read as 6 divides p. I've tried finding a counter example, but I can't find one.
0
votes
3answers
313 views

Prove $x^n-1$ is divisible by $x-1$ by induction

Prove that for all natural number $x$ and $n$, $x^n - 1$ is divisible by $x-1$. So here's my thoughts: it is true for $n=1$, then I want to prove that it is also true for $n-1$ then I use long ...
2
votes
6answers
66 views

Is the following True of False?

Provide a proof if true or a counterexample if false: Let a,b be two integers (not both zero), then the gcd(a,b) divides ay+bx for all for x,y ∈ Z. I tried with several cases such as gcd(5,10) = 5 ...
9
votes
3answers
232 views

Show that $(n!)^{(n-1)!}$ divides $(n!)!$

Show that $(n!)^{(n-1)!}$ divides $(n!)!$ I found this question in a text he was reading about BREAKDOWN OF PRIME FACTORS IN FACT, I decided many years, have posted some here to help, but this ...
1
vote
1answer
30 views

Computations question

a) Determine the prime factorizations of 3850 and 4125 b) Find the value of d = gcd(3850,4125) c) List all the positive divisors of d This is what I have so far. a) 3850: 11, 5, 5, 7, 2 4125: ...
1
vote
2answers
30 views

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.
21
votes
10answers
1k views

Prove if $56x = 65y$ then $x + y$ is divisible by $11$

If $x$ and $y$ are natural numbers, and $56x = 65y$, prove that $x + y$ is divisible by $11$. I tried taking the $\gcd(56x,65y)$ using the Euclidean algorithm, but I got nowhere with it and do not ...
1
vote
3answers
58 views

If $d$ is a common divisor of $m$ and $n$, then so it is of $n$ and $m-n$

I am having trouble proving the following statement: Prove that for all integers $m$ and $n$, if $d$ is a common divisor of $m$ and $n$ (but $d$ is not necessarily the GCD) then $d$ is a common ...
3
votes
2answers
123 views

Defining the Greatest Common Divisor using Symbolic Notation

I am trying to write the definition of greatest common divisor using symbolic notation. Here is my current attempt: $d = gcd(m,n) \Leftrightarrow d \in Z \wedge max(d | m \wedge d | n)$ Any help or ...
0
votes
1answer
35 views

Factorization of GCD

I'm working on a question about factorization of a GCD. Let x = p$^{n1}_1$ ... p$^{nk}_k$ Is it correct to answer this with: p$^{n1}_1$ + $^{m1}_1$ ... p$^{nk}_k$ + $^{mk}_k$ ?
0
votes
1answer
694 views

Suppose a, b and n are positive integers. Prove that (a^n) | (b^n) if and only if a | b. [duplicate]

Suppose $a, b$ and $n$ are positive integers. Prove that $a^n\mid b^n$ if and only if $a \mid b$. I have: $$a^n\mid b^n$$ $$\implies b^n = a^n \cdot k$$ $$\implies \sqrt[n]{b^n}=\sqrt[n]{a^n}\cdot ...
1
vote
1answer
25 views

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 ...
2
votes
3answers
90 views

For every integer $n$, the remainder when $n^4$ is divided by $8$ is either $0$ or $1$.

I am trying to prove the following statement: For every integer $n$, the remainder when $n^4$ is divided by $8$ is either $0$ or $1$. So far I have figured out that $n^4 = 8m$ or $n^4 = 8m + ...
2
votes
2answers
78 views

Does $\pi \ | \ 2 \pi$

Does $\pi$ divide $2 \pi?$ Clearly $\frac{2 \pi}{\pi}=2$ and 2 is an integer, so it would seem to make sense to say that $\pi \ | \ 2 \pi$. Does it make sense to write, for example, $$\pi \ | \ x ...
0
votes
4answers
135 views

Prove that $53^{53}-33^3$ is divisible by $10$

Prove that $53^{53}-33^3$ is divisible by $10$ I don't know modular arithmetic, so I tried things like that: $53^3 \cdot 53^{50}-33^3=(33+20)^3 \cdot 53^{50}-33^3=(33+20)(33+20)(33+20)\cdot ...
7
votes
3answers
149 views

centenes of $7^{999999}$

What is the value of the hundreds digit of the number $7^{999999}$? Equivalent to finding the value of $a$ for the congruence $$7^{999999}\equiv a\pmod{1000}$$
4
votes
1answer
70 views

Methods for finding a relatively prime integer

Here's the problem: Given a prime $p$ and an integer $x$, find an integer $c$ such that $gcd(x+c,p\#)=1$ where $p\#$ is the primorial for $p$. It is straight forward to solve this problem using ...
7
votes
2answers
119 views

Does the $\gcd(2n-1,2n+1)=1?$

I am posting this to ask if my proof is correct as I haven't taken number theory in a year and I feel a bit rusty. If it isn't correct, please tell me where I went wrong so I can fix it. I want to ...
1
vote
2answers
72 views

Prove that $n^n$ is not divisible by $n!$

How can I prove that $n^n$ is not divisible by $n!$ for $n \geq 3$.
1
vote
1answer
39 views

polynomial division, gcd, question

We are asked to show that there are polynomials $p,q \in Q[t]$ such that: $p(t)*(t^4+2t^2+1)+q(t)*(t^4-3t^2-4) = t^2+1$ Is the answer the same for $t+5$ instead of $t^2+1$? What I tried doing: I ...
3
votes
3answers
601 views

How to divide by 12 quickly?

Let $n\in\mathbb N$ be divisible by 12 and $n/12<100$. Is there a way of computing $n/12$ rather quickly using mental arithmetic (e.g. for 972/12, 1044/12, etc.)? For example, the number 11 seems ...
3
votes
1answer
116 views

Divisibility by 37 proof

$\overline {abc}$ is divisible by $37$. Prove that $\overline {bca}$ and $\overline {cab}$ are also divisible by $37$. $$\overline {abc} = 100a + 10b + c$$ $$\overline {bca} = 100b + 10c + a$$ ...
1
vote
2answers
65 views

Number theory proof with modular arithematic [closed]

What is the proof for: If p is an odd prime, show that $$1^n+2^n+3^n+...+(p-1)^n \equiv 0 (\mod p)$$ if $p-1$ does not divide $n$ or $\equiv -1 (\mod p)$ if $p-1$ divides $n$.
1
vote
1answer
23 views

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 ...