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
2answers
184 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
57 views

Divisiblity 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
249 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
51 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
118 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
180 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
54 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
404 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
132 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
73 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
103 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
180 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
55 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
72 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
73 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
70 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
375 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
201 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 ...
0
votes
3answers
102 views

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

This is an extremely simple problem but I'm new to this sort of math so I was wondering if anyone could lead me in the correct direction as to how I'd prove this formally?
9
votes
1answer
549 views

Does $n \mid 2^{2^n+1}+1$ imply $n \mid 2^{2^{2^n+1}+1}+1$?

There are two ways to try to prove this. One is in the title, the other is its de Morgan counterpart: $n \nmid 2^{2^{2^n+1}+1}+1 \implies n \nmid 2^{2^n+1}+1$. Disproving it requires only one example ...
0
votes
1answer
30 views

Given a set of numbers $x_1, x_2, \ldots, x_k$, what is the largest number $h$ such that $x_i \bmod{h} = 0$ for all $i$?

I am solving a system of differential equations with respect to length, let's say 0 to $x_{max} = 10$ meters. Now, I want to choose an integration step such that my step will land on each of the ...
-1
votes
1answer
52 views

Demonstration, $70\mid 101^{6n}-1\;\;\forall n\in\mathbb{N}$ [closed]

$70\mid 101^{6n}-1\;\;\forall n\in\mathbb{N}$ Demonstration: $$101\equiv 31\pmod{70}\\101^2\equiv31^2\equiv961\equiv51\pmod{70}\\101^{6}\equiv51^2\equiv2601\equiv11??$$
0
votes
0answers
30 views

the division $14^{256}$ by $17$ [duplicate]

What the rest of the division $14^{256}$ by $17$? $$14^2\equiv9\pmod{17}\\14^4\equiv13\pmod{17}\\14^8\equiv16\equiv-1\pmod{17}\\(14^8)^{32}\equiv(-1)^{32}\equiv1\pmod{17}$$The rest is $1$, ...
7
votes
3answers
133 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}$$
3
votes
1answer
81 views

Prove that $x^4+x^3+x^2+x+1 \mid x^{4n}+x^{3n}+x^{2n}+x^n+1$

Problem: Prove that $x^4+x^3+x^2+x+1$ divides $x^{4n}+x^{3n}+x^{2n}+x^n+1$ for all positive $n$ that are not multiples of $5$. I'd like to get some pointers about how to solve this. No full ...
0
votes
2answers
96 views

To prove $6|σ(6n-1) , ∀n∈ \mathbb N$

Let $σ(n)$ denote the sum of all the positive divisors of $n∈ \mathbb N$. I think that $6$ divides $σ(6n-1)$ for all $n∈ \mathbb N$ , but I am not able to prove it. So, a proof of the result (if it ...
3
votes
0answers
67 views

Find the fundamental group and the Alexander polynomial

I would like to find the Alexander polynomial of the link $L$, described below. Let $K(q,r)$ be the $(q,r)$-torus knot embedded on a torus $V$. Inside the torus $V$, consider a smaller solid torus ...
0
votes
2answers
166 views

calculate GCD of very large integers

How i can calculate GCD of two very large integers for example: gcd(31415926534676736647, 438478473847834834784748) either by hand or computer? is there any ...
2
votes
3answers
2k views

Find the sum of all the integers between 1 and 1000 which are divisible by 7

How can I work this one out (with workings)? "Find the sum of all the integers between 1 and 1000 which are divisible by 7" Thanks!
5
votes
2answers
329 views

Prove that if $gcd(a,b)=1$, then $gcd(a^2,b^2)=1$

So, if $gcd(a,b)=1$, then $gcd(a^2,b^2)=1$ means $1=ax+by$, and want to show $a^2x+b^2y=1$. By squaring $1=ax+by$ both sides, I get, $1=(ax)^2+b(2axby+by^2)$. It doesn't help my proof. Please help me ...
0
votes
1answer
58 views

Prove $gcd(a-1,a+1)$

Let $a$ be an integer. After looking at several examples, make a conjecture about the value of $gcd(a-1,a+1)$ and prove it. Ok, I found if $a$ is even, $gcd(a-1,a+1)=1$, if $a$ is odd, ...
0
votes
4answers
104 views

Need to prove that $4\cdot 10^{2n} + 9\cdot 10^{2n-1} + 5$ is divisible by $99$ for all $n \in \mathbb{N} $, using induction.

First, obviously, I figured out the base case. So I have $4\cdot 10^{2n} + 9\cdot 10^{2n-1} + 5 = 99k$ for some $k \in \mathbb{N} $. As for the inductive step, I was thinking about splitting it up ...
1
vote
3answers
32 views

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?
1
vote
5answers
63 views

Prove if $a\mid b$ and $b\mid a$, then $|a|=|b|$ , $a, b$ are integers.

Form the assumption, we can say $b=ak$ ,$k$ integer, $a=bm$, $m$ integer. Intuitively, this conjecture makes sense. But I can't make further step.
1
vote
1answer
90 views

GCD of two numbers

Let us call the largest common divisor of integers $m$ and $n$ by $(m,n)$. For example, $(2,3)=1$ and $(10,15)=5$. Let us assume that $n(n+1)(n+2)$ is a square where $n$ is an integer. Now I want to ...
3
votes
3answers
545 views

Use mathematical induction to prove that 9 divides $n^3 + (n + 1)^3 + (n + 2)^3$; Looking for explanation, I already have the solution.

I have the solution for this but I get lost at the end, here's what I have so far. basis $n = 0$; $9 \mid 0^3 + (0 + 1)^3 + (0 + 2)^2 ?$ $9 \mid 1 + 8$ = true Induction: Assume $n^3 + (n + ...
2
votes
1answer
80 views

Show that there exist infinitely many primes of the form $6k-1$

This is a question on the text book that i have no way to deal with. Can anyone help me? Show that there exist infinitely many primes of the form $6k-1$
1
vote
2answers
131 views

Divisiblilty & Prime Problems [GRE]

if j is divisible by 12 and 10, is j divisible by 24? Answer by either saying yes, no , or Can't be determined. I approached this question as follow: First i found the prime factors of both ...
6
votes
2answers
132 views

Divisibility of Fibonacci numbers

This question is inspired by a Project Euler problem I was working on. Noticing something that did not make sense led me to the conclusion that for all primes $p$ ending in $1$ or $9$, the $(p-1)$st ...
1
vote
1answer
39 views

Integral domain is ufd iff atomic and gcd domain

an Integral domain D is a UFD if and only if D is atomic and gcd domain. I know that a UFD is Atomic, but i don't know how to prove it is a gcd domain. the other side of the proof: I do understand ...
0
votes
2answers
66 views

How to find the remainder of $(2010^{1020} + 1020^{2010})$ divided by $3$

What is the remainder when $2010^{1020} + 1020^{2010}$ is divided by 3?
0
votes
0answers
184 views

Smallest positive integer divisible by and having digit sum equal to some 3-digit number.

Let $p,q,r$ be distinct digits among $1,2,4,6,8$, and consider the integer $pqr = 100p + 10q + r$. Let $N$ be the smallest positive integer that is divisible by $pqr$ and has digit sum equal to ...
2
votes
1answer
73 views

Number of prime divisors in an interval

I've found a problem on a c++ website and I don't know how to solve it. Given an interval [x,y] and a number K I have to find how many numbers from this interval have exactly K distinct prime ...
2
votes
1answer
208 views
3
votes
1answer
75 views

Proof that $n+1$ divides $\sum_{k=1}^n k^q$ for $q > 0$

Since $$\sum_{k=1}^n k = \frac{n\left(n+1\right)}{2}$$ $$\sum_{k=1}^n k^2 = \frac{n\left(n+1\right)\left(2n+1\right)}{6}$$ $$\sum_{k=1}^n k^3 = \frac{n^2\left(n+1\right)^2}{4}$$ ... and so on. Is ...
3
votes
1answer
76 views

Divisibility involving root of unity

Let $p$ be a prime number and $\omega$ be a $p$-th root of unity. Suppose $a_0,a_1, \dots, a_{p-1}, b_0, b_1, \dots, b_{p-1}$ be integers such that $a_0 \omega^0+a_1 \omega^1+ \dots a_{p-1} ...
8
votes
3answers
157 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 ...