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
5answers
527 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
244 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
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?
11
votes
2answers
598 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
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 ...
-1
votes
1answer
107 views

Understanding a proof of the fact that $\binom{n}{k}$ is always a natural number.

Original source of question and solution. Question is on the left, answer is on the right. Question: Notice that all the numbers in Pascal's triangle are natural numbers. Use part (a) to prove by ...
-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$, ...
20
votes
1answer
475 views

Is $\sum_{k=1}^{n} k^k / \sum_{k=1}^{n} k \in \mathbb{N}$ for some $n > 1$?

Let $ A = \sum_{k=1}^{n} k^k $ and $ B = \sum_{k=1}^{n} k$, where $n >1 $ is a positive integer. Is $A/B$ ever an integer?
7
votes
3answers
147 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
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
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 ...
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 ...
0
votes
2answers
460 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
457 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
75 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
108 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
64 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
91 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
713 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
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$
1
vote
2answers
211 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
161 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
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
2answers
73 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
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 ...
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 ...
2
votes
1answer
245 views
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} ...
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 ...
1
vote
3answers
33 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
154 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
227 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
60 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
96 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} = ...
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
35 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.
3
votes
4answers
105 views

Prove $5 \mid 2^{n+1} + 3^{3n+1}$

I tried induction, so I assume the hypothesis and attempt to show $5 \mid 2^{n+2} +3^{3n + 4}$ but this doesn't help. I tried breaking it down into prime factorizations, but I do not see it.
2
votes
2answers
61 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.
3
votes
1answer
117 views

Relationship between divisibility of polynomials and divisibility of its evaluations

Let $f$ and $g$ be primitive polynomials over $\mathbb{Z}$. Decide if the following is true: $f(x) \mid g(x)$ for infinitely many $x\in\mathbb Z$ implies $f\mid g$ as polynomials in ...
1
vote
1answer
46 views

Values of $gcd(a-b,\frac{a^p-b^p}{a-b} )$

I don't know how to prove the following result. Let $p$ be a prime number and let $a,b \in \mathbb Z$ such that $gcd(a,b)=1$ Then $gcd(a-b,\frac{a^p-b^p}{a-b}) = 0 $ or $ p $ I know that ...
2
votes
0answers
57 views

Prove that if $d_1=\gcd(a,b), d_2=\gcd(b,c), d_3=\gcd(c,a), D=\gcd(a,b,c)$, and $L=\operatorname{lcm}(a,b,c)$, then $L= \frac{abcD}{d_1 d_2 d_3}$

I tried to define: $a=d_1x_1$, $b=d_1y_1$; $b=d_2x_2$, $c=d_2y_2$; $c=d_3x_3$, $c=d_3y_3$. then $\operatorname{L.H.S} =d_1d_2d_3x_1x_2x_3=d_1d_2d_3y_1y_2y_3$ $\implies$ $x_1x_2x_3=y_1y_2y_3$; ...
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 ...
0
votes
1answer
31 views

Showing the gcd of Integers can be Distributed

The Question: Use the theorem on classification of subgroups of $\mathbb{Z}$ to prove that, if $a_1,...,a_n \in \mathbb{Z}, gcd(a_1,...,a_n) = gcd(gcd(a_1,...,a_k),gcd(a_{k+1},...,a_n))$ for any $1 ...
4
votes
3answers
187 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!
0
votes
5answers
241 views

Show that if $a^n\mid b^n$, then $a\mid b$.

I have a question from a sample exam I have difficulties to solve: Show that if $a^n\mid b^n$, then $a\mid b$. I don't have any idea how to start. I'd like to get helped. thanks!