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
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
112 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
1answer
59 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
2answers
228 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
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 ...
4
votes
3answers
209 views

The greatest common divisor of $a$ and $b$ is a linear combination of $a$ and $b$. In general, in what kind of ring does this hold?

In $\mathbb{Z}$, the greatest common divisor of $a$ and $b$ is a linear combination of $a$ and $b$. This generalizes to Euclidean domains since Euclid's algorithm works. Moreover this statement ...
2
votes
5answers
505 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$ ...
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
81 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: ...
0
votes
3answers
107 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?
0
votes
1answer
31 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 ...
0
votes
2answers
100 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 ...
-1
votes
1answer
53 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
31 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$, ...
3
votes
0answers
76 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 ...
3
votes
1answer
83 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
402 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 ...
4
votes
2answers
546 views

Showing that gcd does not exist for $3(1+\sqrt{-5})$ and $3(1-\sqrt{-5})$ in $\mathbb Z[\sqrt{-5}]$.

An exercise asks me to show that $3(1+\sqrt{-5})$ and $3(1-\sqrt{-5})$ have no greatest common divisor in $\mathbb Z[\sqrt{-5}]$. I think I have to find two maximal common divisors which are not ...
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
439 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
4answers
107 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 ...
0
votes
1answer
73 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, ...
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
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 ...
1
vote
2answers
104 views

Show that all the integer solution of $a^n = b^m$ are given by $a = t^{m/gcd(n,m)}$ , $b = t ^ {n/gcd(n,m)}$ , for some integer $t$.

The quiz of the course of number theory is coming. But I don't really know where to start to deal with this excercise. Can anyone help me? Question: Let $n$ and $m$ be positive integers. Show that ...
2
votes
1answer
88 views

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

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$
3
votes
3answers
692 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 + ...
1
vote
2answers
193 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
157 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 ...
0
votes
2answers
70 views
1
vote
1answer
50 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
0answers
192 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 ...
4
votes
3answers
185 views

Show that if $a \mid bc$,then $a \mid \gcd(a,b)\gcd(a,c)$.

It is a question from my exam, but i cannot figure out how to prove it. Show that if $a \mid bc$, then $a \mid \gcd(a,b)\gcd(a,c)$. I'd like to get helped. Thanks!
2
votes
1answer
78 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 ...
3
votes
1answer
78 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
77 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} ...
2
votes
2answers
58 views

Divisibility and factorial

If $n = st$ and $s > 0$ and $t > 0$ then prove that $(s!)^t|n!$ . If I replace $n!$ with $ (st)!$ how can I simplify it so that I can show that the division is an integer.
1
vote
3answers
31 views

Division by fractions [duplicate]

Why is it that to divide by a fraction you need to multiply by the reciprocal of that fraction? For instance: $\eqalign{ & 1 \div \frac{1}{3} \cr & = 1 \times 3 \cr & = 3 ...
4
votes
1answer
151 views

Solve $a^3 + b^3 + c^3 = 6abc$

Find solutions for $a^3 + b^3 + c^3 = 6abc$ in $\mathbb{N}$, such that $gcd(a,b,c) = 1$, except for $(1,2,3)$ and its permutations. Using trial and error I found out that if $a,b,c$ are solution ...
2
votes
1answer
68 views

A problem relying on van der Waerden's theorem, and the existence of sums divisible by a given number $n$

Say we are given a sequence of integers $\{a_i\}_{i \in \mathbb{N}}$, as well as a pair of integers $n, m$. How can we show that there always exist positive integers $s, r$ such that the sums $a_s + ...
1
vote
1answer
225 views

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 ...
3
votes
1answer
59 views

Solving $\frac{{2{x^3} - 11x + 6}}{{x - 2}}$ using algebraic juggling

Answer: $\eqalign{ & \frac{{2{x^3} - 11x + 6}}{{x - 2}} = \frac{{2{x^2}(x - 2) + 4{x^2} - 11x + 6}}{{(x - 2)}} \cr & = 2{x^2} + \frac{{4x(x - 2) - 8x + 11x + 6}}{{x - 2}} \cr ...
1
vote
2answers
93 views

Distribution of primes remainders

Naively, I would expect the natural density the number of a fixed prime $p$ with remainder $m$ to the other primes to be uniform $$ d(p,m) = \limsup\limits_{n\rightarrow\infty} \frac{a(n,m)}{n} = ...
2
votes
6answers
112 views

help with this assertion: The only number divisible by 3 and that is prime is 3

I have encountered this phrase within a proof by prime numbers and couldn't figure out if it is true. Is there any proof lurking around for this fact? thanks!
0
votes
1answer
53 views

Divisibility question with 8th powers

so I was assigned a divisibility question for homework. Prove that $27195^8-10887^8+10152^8$ is divisible by $26460$. Am I supposed to use mods? I appreciate the help!
0
votes
2answers
34 views

Divisibility of a power

I'm being asked to prove that if $n|m$ and $a > 1$ then $\frac{a^m-1}{a^n-1}$ is an integer. I would like an algebraic prove of the problem.