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)

4
votes
1answer
270 views

The product of any three consecutive natural numbers is divisible by 9.prove or find a counterexample

can anyone give me feedback on my solution false counterexample: n(n+1)(n+2) let n= 1 1(2)(3) =6 is not divisible by 9 is this correct?
4
votes
5answers
453 views

Prove 24 divides $u^3-u$ for all odd natural numbers $u$

At our college, a professor told us to prove by a semi-formal demonstration (without complete induction): For every odd natural: $24\mid(u^3-u)$ He said that that example was taken from a high ...
4
votes
4answers
233 views

If $b^2$ is the largest square divisor of $n$ and $a^2 \mid n$, then $a \mid b$.

I am trying to prove this: $n$, $a$ and $b$ are positive integers. If $b^2$ is the largest square divisor of $n$ and $a^2 \mid n$, then $a \mid b$. I want to prove this by contradiction, and I ...
4
votes
5answers
739 views

Is it possible to get 1/3 without dividing by 3?

So I need to divide a rectangle into 3 equals parts, but without fractions. It's one of those old "You have two jars of two sizes and need to get an exact amount of some other size" type problems, ...
3
votes
3answers
234 views

A polynomial with integer coefficient

I'm struggling with this question: Suppose $P(x)$ is a polynomial with integer coefficients such that non of the values $P(1),...,P(2010)$ is divisible by $2010$. Prove that $P(n)\neq 0$ for all ...
3
votes
6answers
105 views

Proving $\gcd \left(\frac{a}{\gcd (a,b)},\frac{b}{\gcd (a,b)}\right)=1$

How would you go about proving that $$\gcd \left(\frac{a}{\gcd (a,b)},\frac{b}{\gcd (a,b)}\right)=1$$ for any two integers $a$ and $b$? Intuitively it is true because when you divide $a$ and $b$ by ...
3
votes
1answer
106 views

Find two elements that don't have a gcd in a subring of Gaussian integers

Find two elements in the domain $R := \{ x + 2y \sqrt {-1} \mid x,y \in \mathbb{Z} \}$ that do not have a gcd. I have no idea how to start. But I know if we consider $R^\prime = \{ x + y \sqrt ...
3
votes
6answers
211 views

Proof that $a^5 b - b^5 a$ is divisible by $30$ for any integers $a$ and $b$

I am trying to prove that $a^5\times b - b^5\times a$ is divisible by $3$. The actual task is to prove divisibility by $30$ but I have managed to prove that the expression is divisible by $5$ and $2$. ...
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 ...
3
votes
1answer
84 views

Four fractions of certain factorials give another factorial

Let $n>0$ and $s_n=\sum_{k=1}^n k$. I looked at the expressions $\displaystyle\frac{s_n!}{(s_n-n)!}$ and found that the fraction is another factorial for $k=1,2,3,4$, i.e. ...
3
votes
1answer
1k views

Prove the converse of Wilson's Theorem

... namely that if $n > 1$ and $(n − 1)!\equiv−1\pmod{n}$, then $n$ is prime. This is for a number theory class I'm in at Penn State. My idea is to follow accordingly, but I can't get it ...
3
votes
2answers
347 views

Prove that every integer $n>0$ with $\gcd(n,10) = 1$ has a multiple that can be written with only the digit $9$. [duplicate]

Possible Duplicate: Proof that a natural number multiplied by some integer results in a number with only one and zero as digits The question is as stated. I'm really stumped on it. It seems ...
3
votes
2answers
312 views

Number of Divisor

How to find the Number of divisors of a number 'n' that are also divisible by another number 'k' without looping through all the divisors of n? I tried the following: Stored powers of all prime ...
2
votes
0answers
67 views

Find Gcd summation fast?

Find the value of the summation: $$ val=\left( \sum_{i=1}^a \sum_{j=1}^b\sum_{k=1}^c....\sum_{x=1}^p GCD(i,j,k,..x) \right)$$ Contraints $2\leq$number of summation terms$\leq 500$, $1\leq ...
2
votes
5answers
136 views

Prove that if $6 \mid (2a + 4)$ and $9 \mid (12 + 3b)$ then $3 \mid (a + b)$

Could you help me with the problem below? Prove that if $6 \mid (2a + 4)$ and $9 \mid (12 + 3b)$ then $3 \mid (a + b)$. Thank you!
1
vote
2answers
116 views

Let $d$ be a positive odd integer. Prove that there exists a positive $n \le d$ such that $d | 2^n − 1$.

I'm stuck on this question from my textbook which doesn't even have a solution. Any ideas ?. Help would be much appreciated. $$ d\, \left\vert\right.\, \left(2^{n} − 1\right) $$
1
vote
3answers
139 views

Basic Modulo Question

I've been having trouble with this example while studying for my exams. Why is $$2023^{2297}\equiv 20 \pmod{3953}\;?$$ Thanks so much for any help I can get! The examples solves the answer by ...
0
votes
4answers
156 views

Prove that if a and b are integers, then there are unique integers q and r such that $a = bq + r$, $-|b|/2 < r \le |b|/2$ [closed]

Prove that if a and b are integers, then there are unique integers q and r such that $$a = bq + r,$$ with the restriction that$$-|b|/2 < r \le |b|/2$$
0
votes
1answer
94 views

Two issues of Number Theory

Knowing in Fibonacci sequence$$u_n\mid u_m\Longleftrightarrow n\mid m$$ Question 1: In Fibonacci sequence, show that $$5\mid u_m\Longleftrightarrow 5\mid m$$ Show: $\Longrightarrow$ In ...
0
votes
1answer
79 views

Prime divisibility in a prime square bandtwidth

I am seeking your support for proving (or fail) formally the following homework: Let $p_j\in\Bbb P$ a prime, then any $q\in\Bbb N$ within the interval $p_j<q<p_j^2$ is prime, if and only if ...
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 ...
20
votes
1answer
476 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?
21
votes
10answers
1k views

Prove if $56x = 65y$ then $x + y$ is divisible by $11$

If $x$ and $y$ are natural numbers, and $56x = 65y$, prove that $x + y$ is divisible by $11$. I tried taking the $\gcd(56x,65y)$ using the Euclidean algorithm, but I got nowhere with it and do not ...
4
votes
1answer
236 views

Divisibility of $2^n - 1$ by $2^{m+n} - 3^m$.

For what values of $m,n$ natural, do $2^n - 1$ is divisible by $2^{m+n} - 3^m$? Thank you very much.
8
votes
2answers
2k views

Divisibility Rules for Bases other than $10$

I still remember the feeling, when I learned that a number is divisible by $3$, if the digit sum is divisible by $3$. The general way to get these rules for the regular decimal system is ...
7
votes
1answer
84 views

Bezouts Identity for prime powers

I have two prime powers $2^n$ and $5^n$ for some arbitrary $n$. Their gcd is $1$ but how do I get their integer linear combination which is $1$ in terms of $n$. In other words what will be the ...
5
votes
2answers
139 views

Analogy between prime numbers and singleton sets?

While trying -- in vain -- to write an alternative answer for another question (If $\cup \mathcal{F}=A$ then $A \in \mathcal{F}$. Prove that $A$ has exactly one element.), I discovered the following ...
5
votes
2answers
172 views

How to prove that for all $m,n\in\mathbb N$, $\ 56786730 \mid mn(m^{60}-n^{60})$?

How to prove $\forall m,n\in\mathbb N$: $$ 56786730 \mid mn(m^{60}-n^{60})?$$ Thanks in advance.
3
votes
6answers
2k views

Trick to find multiples mentally

We all know how to recognize numbers that are multiple of $2, 3, 4, 5$ (and other). Some other divisors are a bit more difficult to spot. I am thinking about $7$. A few months ago, I heard a simple ...
18
votes
3answers
731 views

My first induction proof (very simple number theory). Please mark/grade.

What do you think about my first induction proof? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof First, introducing a predicate ...
9
votes
3answers
231 views

Show that $(n!)^{(n-1)!}$ divides $(n!)!$

Show that $(n!)^{(n-1)!}$ divides $(n!)!$ I found this question in a text he was reading about BREAKDOWN OF PRIME FACTORS IN FACT, I decided many years, have posted some here to help, but this ...
3
votes
0answers
77 views

Prove the equality

Given $a,b,c,d$ are positive integers such that $a^2+b^2+c^2+d^2-ab-bc-cd-da$ is divisible by $abcd$. Prove that $a=b=c=d$.
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)} + ...
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 ...
2
votes
3answers
91 views

Divisor in $\mathbb{C}[X]$ $\implies$ divisor in $\mathbb{R}[X]$?

let $P \in \mathbb{R}[X]$ be a real polynomial divisible by a polynomial $Q \in \mathbb{R}[X]$ in $\mathbb{C}[X]$. How can I easily show that $P$ is also divisible by $Q$ in $\mathbb{R}[X]$? A simple ...
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 ...
2
votes
2answers
381 views

If $a$ is even and $b$ is odd then $\gcd(2^{a}+1,2^{b}+1)=1$

How to prove that: If $a$ is even and $b$ is odd then $\gcd(2^{a}+1,2^{b}+1)=1$ This statement is generalization of the statement from my previous question. I have checked for many $(a,b)$ ...
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.
0
votes
2answers
58 views

Divisibility of sum of powers: $\ 323\mid 20^n+16^n-3^n-1\ $ for which $n?$

I found this question in my Math Challenge II Number Theory packet: Find all positive integers $n$ that satisfy $323|20^n+16^n-3^n-1$. I don't even have any idea how to approach this question. Any ...
14
votes
6answers
1k views

Divisibility criteria of 24. Why is this?

I am currently familiar with the method of checking if a number is divisible by $2, 3, 4, 5, 6, 8, 9, 10, 11$. While Checking for divisibility for $24$ (online). I found out that the number has to ...
8
votes
7answers
1k views

Proof for divisibility by $7$

One very classic story about divisibility is something like this. A number is divisible by $2^n$ if the last $n$-digit of the number is divisible by $2^n$. A number is divisible by 3 (resp., by ...
4
votes
1answer
130 views

$\sum\limits_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k}$ isn't divisible by 5

I have no idea Prove that for any $n$ natural number this sum $$\sum\limits_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k}$$ isn't divisible by $5$. $\begin{array}{l} \left( {1 + x} \right)^{2n + 1} - ...
4
votes
2answers
136 views

Proving $\gcd( m,n)$=1 [duplicate]

If $a$ and $b$ are co prime and $n$ is a prime, show that: $\frac{a^n+b^n}{a+b}$ and $a+b$ have no common factor unless $a+b$ is a multiple of $n$ Also enlighten me why $n$ has to be prime so that ...
4
votes
1answer
97 views

how to find all $n \in \Bbb N$ such that $n(n+1)\mid(n-1)! $

how to find all $n \in \Bbb N$ such that $n(n+1)\mid(n-1)! $
4
votes
2answers
733 views

Trying to prove that $p$ prime divides $\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$

So I'm trying to prove that for any natural number $1\leq k<p$, that $p$ prime divides: $$\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$$ Writing these choice functions in ...
2
votes
3answers
88 views

For every integer $n$, the remainder when $n^4$ is divided by $8$ is either $0$ or $1$.

I am trying to prove the following statement: For every integer $n$, the remainder when $n^4$ is divided by $8$ is either $0$ or $1$. So far I have figured out that $n^4 = 8m$ or $n^4 = 8m + ...
2
votes
2answers
279 views

Determine the number of factors for extremely large numbers.

An offshoot from a related question, is there a way to determine the number of possible factors (odd, even, prime, etc.) for extremely large integers without actually factoring them? Even an ...
2
votes
3answers
341 views

Factoring extremely large integers.

The question is about factoring extremely large integers but you can have a look at this question to see the context if it helps. Please note that I am not very familiar with mathematical notation so ...
2
votes
3answers
565 views

16 digit numbers divisible by 17

I wanted to know about the $16$ digit numbers those are divisible by $17$ and when this $16$ digit number is broken in groups of $4$ those groups of four are also divisible by $17$ and a check to ...
1
vote
1answer
85 views

If $a,b \in\mathbb N$ and $\gcd(a,b)=1$, prove that $\gcd(a+b;a^2+b^2)= 1$ or $2$.

If $a,b \in\mathbb N$ and $\gcd(a,b)=1$, prove that $\gcd(a+b,a^2+b^2)$ is always equal to either 1 or 2, where $\gcd$ is the greatest common divisor. I haven't really ever solved a problem like this ...