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)

1
vote
1answer
158 views

The proportion of numbers not divisible by prime numbers with respect to primorial numbers.

Looking at the interval of the natural numbers $ [1, p_{n}$#$] $; $\frac{1}{2}$ of the elements of this set will be even, and $\frac{1}{2}$ will be odd. $\frac{1}{3}$ of the elements of this set will ...
1
vote
2answers
99 views

Integer division

I think I found a mistake in the princeton review "Cracking the GRE" 2014 edition on page 408. The problem is as follows: If $\frac{13!}{2^x}$ is an integer, which of the following represents all ...
3
votes
4answers
60 views

Is $\mbox{lcm}(a,b,c)=\mbox{lcm}(\mbox{lcm}(a,b),c)$?

$\newcommand{\lcm}{\operatorname{lcm}}$Is $\lcm(a,b,c)=\lcm(\lcm(a,b),c)$? I managed to show thus far, that $a,b,c\mid\lcm(\lcm(a,b),c)$, yet I'm unable to prove, that $\lcm(\lcm(a,b),c)$ is the ...
0
votes
2answers
388 views

For all integers a, b, c, if a | b and b | c then a | c. [duplicate]

Is this T or F? and most importantly, why? I'll be using any answers for a basis or completely my other questions, since my understanding is still a little poor.
4
votes
3answers
270 views

How does one attack a divisibility problem like $(a+b)^2 \mid (2a^3+6a^2b+1)$?

In my current line of investigation, I am running into [many] divisibility questions like the one in the title, i.e. $$ (a+b)^2 \mid (2a^3+6a^2b+1), \qquad(\star) $$ where $a > b \ge 1$ are ...
0
votes
1answer
56 views

Suppose $gcd(a,n)=1$. If $a^x\equiv b\pmod n$ and $xy\equiv 1\pmod {\phi(n)}$, show that $a\equiv b^y\pmod n$.

My midterm exam is coming and I have some problem in dealing with this kind of question. This is an exercise on my text book and not a homework. Suppose $gcd(a,n)=1$. Question(a) If $a^x\equiv ...
0
votes
1answer
30 views

A semiprime only has $4$ factors

It seems quite trivial, but I can't figure out how to explain that in general a semiprime $pq$ only has $4$ factors (namely $1, p, q, pq$). Can anyone give me a small proof?
1
vote
1answer
52 views

Show that $\frac{(m+n)!}{m!n!}$ is an integer whenever $m$ and $n$ are positive integers using Legendre's Theorem

Show that $\frac{(m+n)!}{m!n!}$ is an integer whenever $m$ and $n$ are positive integers using Legendre's Theorem. Hi everyone, I seen similar questions on this forum and none of them really talked ...
1
vote
2answers
358 views

Show that if $a$ and $b$ are positive integers with $(a,b)=1$ then $(a^n, b^n) = 1$ for all positive integers n [duplicate]

Show that if $a$ and $b$ are positive integers with $(a,b)=1$ then $(a^n, b^n) = 1$ for all positive integers n Hi everyone, for the proof to the above question, Can I assume that since $(a, b) = ...
0
votes
1answer
234 views

$\gcd(ab,c)$ equals $\gcd(a,c)$ times $\gcd( b, c)$

Let $a,b,c$ be integers, prove that if $\gcd(a,b) =1$ then $\gcd(ab,c) = \gcd(a,c)\times\gcd(b,c)$ I don't know what to do after I got the combinations of $ab$ and $c$.
5
votes
2answers
97 views

gcd Calculations

Let $a, b, c$ be integers. Prove that if $\gcd(a,b)=1$ then $\gcd(ab,c) = \gcd(a,c) \gcd(b,c)$ First time asking here. I'm not sure what your policies are on general homework help but I truly am ...
0
votes
1answer
164 views

Divisibility Discrete Math

For all integers a, b, c, if a | (b + c), then a | b and a | c True or false? Im assuming it's false because if you make a=2 b=3 and c=4, it won't work
1
vote
1answer
226 views

Show that if $a$ is an even integer and $b$ is an odd integer then $(a, b) = (a/2, b)$

Show that if $a$ is an even integer and $b$ is an odd integer then $(a, b) = (a/2, b)$ Hi everyone, I would like to know if my assumption is justified for answering the above question. Any ...
3
votes
0answers
257 views

Show that if both a, b are even integers not both 0, then $(a, b) = 2 (a/2, b/2)$

Show that if both a, b are even integers not both 0, then $(a, b) = 2 (a/2, b/2)$. Hi there, I want to know if the following proof I have is strong enough, or if I'm making false assumptions :|. ...
2
votes
1answer
70 views

A question on primes and divisibility

The question goes as follows: Prove that for any prime $p\geq 5$, $p^2-1$ will be divisible by $12$. I think I have a solution but I just wanted to double check with you guys. My attempt: If $p$ ...
3
votes
2answers
91 views

$\gcd(c^a + 1, c^b + 1)$ for even $a$ and $b$?

Following on this question, what is the Greatest Common Denominator of $c^a + 1$ and $c^b + 1$, where $a, b, c \in N$. I know that for odd a and b, we have $\gcd(c^a + 1, c^b + 1) = c^{\gcd(a, b)} + ...
1
vote
1answer
87 views

If $\gcd(f(x), g(x)) = 1$, then $\gcd(h(x)f(x), g(x)) = \gcd(h(x), g(x))$

This is not homework, but I would just like a hint. The question asks Let $f(x), g(x), h(x) \in F[x]$ (where $F$ is a field), and $\gcd(f(x), g(x)) = 1$. Show that $\gcd(f(x)h(x), g(x)) = ...
0
votes
0answers
28 views

The product of $i$ consecutive natural numbers is divisible for $i!$ [duplicate]

There is a theorem that I've used it a few times, and never saw a demo of it, and when I tried, I could not, commenting with a teacher, it would not give me much attention and said it would use the ...
1
vote
4answers
113 views

If $k^2-1$ is divisible by $8$, how can we show that $k^4-1$ is divisible by $16$?

All is in the title: If $k^2-1$ is divisible by $8$, how can we show that $k^4-1$ is divisible by $16$? I can't conclude from the fact that $k^2 - 1$ is divisible by $8$, that then $k^4-1$ is ...
3
votes
2answers
56 views

Proof of statement: If $a\mid b$ and $a\mid c$, then $a \mid b+c$

Statement: If $a$ divides both $b$ and $c$, then $a$ divides $b+c$ Proof: Assume that $a$ does not divide $b+c$. Then there is no integer $k$ such that $ak=b+c$. However, $a$ divides $b$, so $am=b$ ...
3
votes
3answers
645 views

Proof if $n$ is divisible by $3$ then the sum of the digits of $n$ are a multiple of $3$

Proof if $n$ is divisible by $3$ then the sum of the digits of $n$ are a multiple of $3$. What is the name of that theorem and who performed that theorem? I don't understand the proof given here: ...
0
votes
0answers
237 views

Prove that $gx^2 \sim f$

Let $f(x,y) = ax^2 + bxy + cy^2$ be a positive semidefinite quadratic form with determinant $= 0$. Let $\operatorname{gcd}(a,b,c) = g$. Show that $gx^2 \sim f$. I'm not sure how to do this. All I ...
1
vote
5answers
109 views

Euclidean Algorithm Question

So I have been asked to find $d=(a,b)$ when $a=1109$ and $b=4999$ and express $d$ as a linear combination of $a$ and $b$ Well I have worked out that $d=1$ but I am struggling to express $d$ as a ...
6
votes
1answer
69 views

Is this divisibility test for 4 well-known?

It has just occurred to me that there is a very simple test to check if an integer is divisible by 4: take twice its tens place and add it to its ones place. If that number is divisible by 4, so is ...
0
votes
1answer
64 views

Simple divisibility problem in elementary number theory

Find all positive integers $n$ such that $n+2009$ divides $n^2+2009$ and $n+2010$ divides $n^2+2010$. I'm kind of new in number theory and got stuck in this simple problem. I'm almost sure that the ...
6
votes
3answers
120 views

Why if $n \mid m$, then $(a^n-1) \mid (a^m-1)$?

My Number Theory book says that for $n, m$ be positive integers and $a>1$, then $(a^n -1)\mid(a^m -1)$ if and only if $n\mid m$. I understand the proof for only if part, but in if part the ...
1
vote
2answers
97 views

If $n$ divides $2^{2^{n} +1}+1$ $\to$ $n$ divides $2^{n}+1$?

Find a counterexample to show that the following implication is not valid. if $n$ divides $2^{2^{n} +1}+1$ $\to$ $n$ divides $2^{n}+1$ And show how to use it. This question appeared on the topic ...
6
votes
5answers
301 views

How can I prove by induction that $9^k - 5^k$ is divisible by 4?

Recently had this on a discrete math test, which sadly I think I failed. But the question asked: Prove that $9^k - 5^k$ is divisible by $4$. Using the only approach I learned in the class, I ...
1
vote
2answers
206 views

Rabin's test for polynomial irreducibility over $\mathbb{F}_2$

I know that $f(x) = x^{169}+x^2+1$ is a reducible polynomial over $\mathbb{F}_2$. I want to show this using Rabin's irreduciblity test. First, I then have to check if $f$ is a divisor of ...
0
votes
2answers
204 views

Show that if $10$ divides into $n^2$ evenly then $10$ divides into $n$ evenly

I'm not sure how to show that if $10$ divides into $n^2$ evenly, then $10$ divides into $n$ evenly.
0
votes
1answer
68 views

Divisibility of a number by $(4k+3)$ in minimum time

Please suggest any algorithm with minimum time complexity to check whether a number $n$ is divisible by at least one $(4k+3)$ where $k>0$ is integer and $(4k+3)\le n$?
1
vote
0answers
34 views

College number theory problem - need a pointer! [duplicate]

$n$ divides $2^{2^n+1}+1$ $\implies n$ divides $2^{2^{2^n+1}+1}+1$? There are two ways to try to prove this. One is above, the other is its de Morgan counterpart: $n$ doesn't divide ...
1
vote
1answer
292 views

Show that the gcd of an odd integer and an even integer is odd

I am using the definition of odd and even integers along with bezout's theorem and I end up with something of the form $d=(2k)m+(2l+1)p$ where $a=2k$ and $b=2l+1$. I've tried to use contradiction as ...
0
votes
1answer
53 views

Is this proof correct? (GCD)

If this proof is incorrect can someone tell me what is wrong with it, and which step is incorrect. Let a, b ∈ℤ If gcd(a, b) = 35, then 25 ∤ a or 25 ∤ b. Proof Consider the contrapositive: if 25|a ...
2
votes
6answers
121 views

Prove that $6$ divides $n(n + 1)(n + 2)$

I am stuck on this problem, and was wondering if anyone could help me out with this. The question is as follows: Let $n$ be an integer such that $n ≥ 1$. Prove that $6$ divides $n(n + 1)(n + 2)$. ...
3
votes
1answer
200 views

GCD of Fibonacci-like recurrence relation

What is the greatest common denominator of $t(c^a)$ and $t(c^b)$, if $t(n) := k_1 f_1^n + k_2 f_2^n $? I already found out that the gcd is always a member of $t(n), n \in N $. $t(n)$ was originally ...
0
votes
4answers
58 views

Prove that if $3|a^2-b^2$, $8|a^2-b^2$, then $24|a^2-b^2$.

if $3|a^2-b^2$, $8|a^2-b^2$, then $24|a^2-b^2$. Is it something can be proved? If so, please give me a guide line.
2
votes
5answers
461 views

Suppose that $5\leq q\leq p$ are both prime. Prove that $24|(p^2-q^2)$. [duplicate]

Suppose that $5\leq q\leq p$ are both prime. Prove that $24|(p^2-q^2)$. This is what I got so far. I figured that since $p,q$ are bigger than $5$, there are only odd primes for this conjecture. ...
3
votes
3answers
34 views

$7^n+5*7^m$ and $2*7^n+4*7^m$ are divisible by 3

While I was helping my daughter with some advanced task from homework, we came to assumption in title. Experiment shows that it is most likely true. But I can't came up with formal proof. Any ideas?
1
vote
1answer
148 views

How to prove Greatest Common Divisor using Bézout's Lemma

The problem is to prove the following If $\gcd(a,b) = c$, then $\gcd(a^m, b^m) = c^m$ I know that this can be solved easily by proving that $c\mid a \implies c^m \mid a^m$ and $c\mid b \implies ...
1
vote
3answers
74 views

Prove that any number of the form $a_3a_2a_1a_3a_2a_1$ is divisible by 91.

Prove that any number of the form $a_3a_2a_1a_3a_2a_1$ is divisible by 91. I got up to $a_3a_2a_1a_3a_2a_1$ = 1000001$a_3$ + 10010$a_2$ + 1100$a_1$. However none of the coefficients are divisible ...
3
votes
2answers
110 views

Prove Divisibility test for 11 [duplicate]

Prove Divisibility test for 11 "If you repeatedly subtract the ones digit and get 0, the number is divisible by 11" Example: 11825 -> 1182 - 5 = 1177 1177 -> 117 - 7 = 110 110 -> 11 - 0 = 11 11 ...
2
votes
2answers
73 views

Prooving by absurd that $d \nmid 4,5,10, 20$

What I'm trying to solve is the following: Given that $(a:b) = 2$, proove that $(a^2 + 2b^2+10:20) = 2$. So, basically, I think that what I need to do is to show that if $d = a^2 + 2b^2 + 10$, then ...
0
votes
2answers
216 views

Given that $gcd(a,b)=1$, prove that $gcd(a+b,a^2-ab+b^2)=1$ or $3$, also when will it equal $1$? [duplicate]

It is an exercise on the lecture that i am unable to prove. Given that $gcd(a,b)=1$, prove that $gcd(a+b,a^2-ab+b^2)=1$ or $3$, also when will it equal $1$?
0
votes
1answer
58 views

finding factors for gcd

To compute $gcd(25, 11)$, Euclid's algorithm would proceed as follows: $$\underline{25} = 2 \cdot \underline{11}+3$$ $$\underline{11} = 3 \cdot \underline{3}+2$$ $$\underline{3} = 1 \cdot ...
0
votes
1answer
73 views

Prove divisibility for general equation of sucession

I have the following problem: Prove that given the following succession: $a_1 = 2, a_2 = 4, a_{n+2} = (n+1)a_{n+1} + (n-1)a_n, \forall n \in \mathbb{N}$ then, it follows that $\forall n \in ...
1
vote
3answers
78 views

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 ...
0
votes
1answer
79 views

Find Greatest Common Divisor and Least Common Multiple

Find GCD (320, 112) and LCM[320, 112]. Solve the equation 320x + 112y = a in the following situations: (i) a = 32 (ii) a = 10. Using Euclids Algorithm to find the GCD I have the following: ...
2
votes
5answers
482 views

Show that the sum of squares of four consecutive natural numbers may never be a square.

Show that the sum of squares of four consecutive natural numbers may never be a square. I know (and I have the proof) a theorem that says that every perfect square is congruent to $0, 1$ or $4$ ...
4
votes
4answers
233 views

Find the smallest natural number that leaves residues $5,4,3,$ and $2$ when divided respectively by the numbers $6,5,4,$ and $3$

Find the smallest natural number that leaves residues $5,4,3,$ and $2$ when divided respectively by the numbers $6,5,4,$ and $3$. I tried ...