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)

0
votes
1answer
35 views

Number theory problem divides

In class today we were talking about proving the definition of 'divides' and the teacher never got to finish this proof. if a divides b^2 , then a divides b. First line was: Let a and b be ...
7
votes
8answers
268 views

Why is $2x^3 + x$, where $x \in \mathbb{N}$, always divisible by 3?

So, do you guys have any ideas? Sorry if this might seem like dumb question, but I have asked everyone I know and we haven't got a clue.
5
votes
2answers
77 views

GCD and the Riemann zeta funtion

I'm completely stuck on this one, as I'm just starting with analytic number theory: How to write $$\sum_{a\in\mathbb{N}}\sum_{b\in\mathbb{N}}\frac{(a,b)}{a^sb^t}$$ in terms of the Riemann zeta ...
5
votes
2answers
99 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
2answers
41 views

Concatenation of strings

We have two strings A and B. We have to find if for some n,m A concatenated n times equals B concatenated m times or not. I have made an interesting observation but am unable to prove it.It appears ...
1
vote
0answers
89 views

When is a number like “ddd…ddd”+1 (where d is a digit) a perfect square or a prime?

Inspired by Is the number $333, 333, 333, 333, 333, 333, 333, 333, 334$ a perfect square?, I wonder when numbers like these are perfect squares. Certainly, all numbers of the form $000...0001$ are ...
1
vote
2answers
215 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
1answer
91 views

Explanation of proof common divisor divides gcd needed

I have been given a proof that uses the gcd to show that there is no biggest prime. However (coming from a less mathematical background) I am having trouble actually understanding what it means and ...
-1
votes
1answer
105 views

What is the LCM of $3^{2001}-1$ and $3^{2001}+1$?

What is the LCM of $3^{2001}-1$ and $3^{2001}+1$? I can not get whether the GCF is $2$ or more than that.
0
votes
2answers
92 views

How to show the existence of a number with certain divisibility conditions between two multiples?

How can we show that between two even natural numbers they're exists a natural number that isn't even? How can we show that they're exists a natural number that is odd and not divisible by 3, between ...
0
votes
2answers
83 views

How can I prove that 4k^2 mod 3 is always = 1

I have a statement $n \in N, \;n^2 \mod 3 = \{0, 1\}$, which basically says that any natural number $n$ when squared will have a remainder after dividing by $3$ of either $0$ or $1$. From here I ...
1
vote
1answer
166 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
1answer
151 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 ...
33
votes
4answers
1k views

How does the divisibility graphs work?

I came across this graphic method for checking divisibility by $7$. $\hskip1.5in$ Write down a number $n$. Start at the small white node at the bottom of the graph. For each digit $d$ in ...
3
votes
4answers
61 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
429 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.
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)} + ...
0
votes
1answer
32 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?
0
votes
1answer
57 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 ...
1
vote
1answer
775 views

What is wrong with my solution of finding remainder of $50^{(51^{52})}$ when divided by 11?

I used the following method using remainder theorem. (I used method from here: Find the remainder of $128^{1000}/153$.) $$\begin{align} (50^{{51}^{52}})/11 & = (50^{2652})/11 \implies \\ ...
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
384 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
176 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
8
votes
3answers
160 views

How can we find the gcd for elements (binomial coefficient)?

$\gcd\left(\binom{2n}1,\binom{2n}3,\binom{2n}5,\ldots,\binom{2n}{2n-1}\right)$ i want to know what is specialty of such a series.I am not able to generalize the problem solution.Is there any rule for ...
2
votes
4answers
173 views

law of divisibility on $37$

how to find and prove law of divisibility on $37$? Thanks in advance. Added:---- how to prove for$37$ that: Split off the last digit, multiply by 11, and subtract the product from the number that is ...
1
vote
1answer
241 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
284 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
75 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$ ...
1
vote
1answer
90 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)) = ...
3
votes
1answer
204 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
0answers
29 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 ...
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$ ...
1
vote
5answers
117 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 ...
3
votes
3answers
725 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
238 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 ...
6
votes
1answer
70 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
67 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 ...
-1
votes
5answers
769 views

The sequence of integers which are not divisible by 3

It is a formula to generate the sequence of all integers which are not divisible by 3? Additionally, it is a formula to generate the sequence of all integers that are not divisible by 3 nor by 2?
6
votes
3answers
123 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
99 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 ...
0
votes
2answers
208 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.
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 ...
3
votes
1answer
102 views

Proof involving division algorithm

I'm trying to prove the following. Let $m$ and $n$ be positive integers, $n>m$. Prove that if $n$ divided by $m$ leaves remainder $r$, then $2^n - 1$ divided by $2^m-1$ leaves remainder ...
0
votes
1answer
55 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
122 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)$. ...
2
votes
5answers
479 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. ...
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.
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
3answers
75 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
115 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 ...