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
votes
1answer
75 views

Prove or disprove f an integer is divisible by 4, then it is divisible by 8

I need to know if I can prove or disprove if an integer is divisible by 4 then it is divisible by 8,for this question should i just show a value like 12 to show this statement is wrong or what? How ...
3
votes
0answers
48 views

In any set of ten consecutive positive integers, there is one that is coprime with each one of the others [duplicate]

Let $a$ be a postive integer and let $A=\{a,a+1,a+2,\ldots,a+9\}.$ Show that there exists some $i$ such that for any $j\neq i$ we have $(a+i,a+j)=1$
0
votes
2answers
34 views

If a number cannot be…

If there exists such a number which cannot be divided by some other number, which is equivalent to, or smaller than the square root of itself, it is a prime number. This is a rather trivial theorem ...
2
votes
2answers
67 views

Checking whether a number is prime or composite

This is a question that came up while I was doing an exercise. I ended up with the number $$ 200! + 1$$ and I want it to be composite but I don't know of any methods to check whether a number is ...
-1
votes
1answer
47 views

why is 6 divided by 1245 207.5? instead of 207 remainder 3?

Help, 6 / 1245 = 207.5? I did long division to get my answer. But when i calculate it myself i end up with 207 remainder 3 ,how does that translate into .5? I don't understand.
2
votes
1answer
26 views

If $x$ divides $x-z$, then $x$ divides $z$

For any integer x and z , if $x|(x-z)$ then $x|z$ My attempt: suppose $x|(x-z),$ let $y= x-z$ $x|y $ means there is any integer r such that $y=r*x$ So $ x-z=rx $, which equals $(x-z)/(x) =r $ ...
2
votes
3answers
47 views

Why test of divisible by $12$ works with $3$ and $4$ but not with $2$ and $6 ?$

Test of divisible by $4 ,$ last two digit must be divisible by $4 ,$ since $100$ is always divisible by $4$ remaining two digit $,$ we need to check $.$ Test of divisible by $3 ,$ sum digits must be ...
0
votes
0answers
24 views

What number from an integer range has the most divisors? [duplicate]

I've been wondering. What number from an integer range (-2 147 483 647/+2 147 483 647) has the most divisors and how many is that?
1
vote
2answers
46 views

Divisibility of a series

I use the notation $123 \dots (z)$ to represent a number that looks like a concatenated string of consecutive integers up to $z\in \mathbb{N}$. E.g. $123 \dots (15)$ denotes $12346789101112131415$. I ...
2
votes
5answers
28 views

Prove divisibility: if $a\mid (b-d)$ and $a\mid (c-e)$, then $a\mid (bc-de)$

I have this math question. It states: Show that for any $a , b ,c, d, e \in \mathbb{Z^+}$, if $a\mid (b-d)$ and $a\mid (c-e)$, then $a\mid (bc-de)$. I'm not 100% sure as to how to start this ...
0
votes
0answers
67 views

Number Theory Homework: Find 3 consecutive integers…

I have this problem assigned for homework, and I'm a bit confused as to how to solve it: Obtain three consecutive integers, the first of which is divisible by a square, the second by a cube, and the ...
3
votes
1answer
192 views

Prove that if 2 divides $x^2-5$ then 4 divides $x^2-5$

so I have to prove this and I use two different types of proof and I came to a contradicting result. Can someone point out an error I made? Using a direct proof: If 2 divides $x^2-5$ than $x^2-5=2k$ ...
0
votes
1answer
26 views

Divisibility proof with co-prime numbers

Let $a,b$ be co-prime. Prove that for every integer $n > a$ it is true that $a | (n + kb)$ for some $k$ with $0 <= k < a$. I have a feeling this is very basic stuff and I feel like there is ...
1
vote
2answers
38 views

Only prime numbers $a$ (and $1$) have the property that $a\mid bc$ implies $a\mid b$ or $a\mid c$

I'm trying to prove this statement but I don't know where to start. The problem says, Let $a$,$b$, and $c$ be positive integers. Suppose that, for any $b$ and $c$, whenever $a\mid bc$, either $a\mid ...
0
votes
2answers
48 views

Efficient way to check if large number is divisible by 3

If Mp=2p-1 is prime ⇒ ⇒ 2p-2⋮6 or 2p⋮6 ⇒ ⇒ 2p-1-1⋮3 or 2p-1⋮3 ⇒ ⇒ 2n-1⋮3 or 2n⋮3, n=p-1 In order to pick huge values for p to test if Mp is a prime number, I believe this is a good preliminary ...
0
votes
1answer
27 views

subtract two 4-digit numbers and obtain the sum of the digits always 18

Let (abcd) and (dcba) be 4-digit numbers and (abcd)-(dcba)= (xyzt) show that the sum of the number (xyzt) is always 18. I think we will use divisibility rules but i could not succeed...
3
votes
2answers
84 views

Showing that if $(a,b)=1$ and if $a\mid c$ and $b\mid c$ then $ab \mid c$, in GCD domains

Is there a proof for the problem below? $R$ is a commutative, integral domain with unity in which for each pair $a,b\in R$, g.c.d. $(a,b)$ exists. I want to show that if $(a,b)=1$ and if $a\mid c$ ...
2
votes
2answers
42 views

Prove $3 \mid x-2 \implies 3 \mid (x^2 - x+1)$ using division algorithm

I can't figure out how to prove the following implication using the division algorithm: $$3 \mid x-2 \implies 3 \mid (x^2 - x+1)$$ It seems simple enough. Does anyone know how?
1
vote
0answers
24 views

Unwind quaternion multiplication

I am trying to understand quaterions division. Imagine I have the following equation, where every member is a quaternion: $$Q = (qq_1)(qq_2)...(qq_n)$$ I suppose that, if I maintain the order of ...
-2
votes
2answers
176 views

Divisibility of subsets of the set $1, 2, 3, …, n$ [closed]

Let $n$ be an even positive integer. Can one divide the numbers $1, ..., n$ into three nonempty groups, so that the sum of numbers in the first group is divisible by $n + 1$, in the second one by $n + ...
2
votes
2answers
59 views

if $5\nmid a$ or $5\nmid b$, then $5\nmid a^2-2b^2$.

I have a homework as follow: if $5\nmid a$ or $5\nmid b$, then $5\nmid a^2-2b^2$. Please help to prove it. EDIT: MY ATTEMPT Suppose that $5\mid a^2-2b^2$, then $a^2-2b^2=5n$,where $n\in Z$, then ...
4
votes
2answers
66 views

Simple question about dividing by zero, $y=\frac{x}{x}$ when $x=0$

Is there a rule that says you have to simplify equations before evaluating them? Would $y=\frac{x}{x}$ at $x=0$ be $1$ or undefined, since without reducing it, you'd divide by $0$. I know the equation ...
2
votes
3answers
56 views

Prove divisibility with gcd: If $ar+bs=d=\gcd(a,b)$, then $r$ and $s$ are relatively prime

I have this math problem. The question is: Suppose that $a$ and $b$ are positive integers, with $d = \gcd(a, b)$. Suppose that there exists integers $r$ and $s$ so that $ar + bs= d$. We ...
8
votes
2answers
179 views

If a divisor of $pq-1$ divides the LCM of $p-1$ and $q-1$, then it also divides the GCD of these two numbers

Suppose that $p,q$ are distinct odd primes. Suppose an integer $k$ divides $pq-1$ and also $k|\operatorname{lcm}(p-1,q-1)$. Show that $k|\operatorname{gcd}(p-1,q-1)$. I've spent ages looking at ...
1
vote
0answers
25 views

Prove that $AB\mid CD$

I have this math question that I'm kind of confused on. This is the question: Let $A, B, C$ and $D$ be integers with $A \mid C$ and $B \mid D$ show that $$ AB \mid CD. $$ I'm not 100% sure ...
7
votes
3answers
259 views

Proof that $n+k+3$ divides $n(n+1)(n+2)(n+3) - k(k+1)(k+2)(k+3)$.

I'm looking for proof that $$ (n+k+3) \mid n(n+1)(n+2)(n+3) - k(k+1)(k+2)(k+3)\\ n,k \in \mathbb N^*, n>k $$ I tried using induction, but i'm not sure how it would work with 2 parameters.
1
vote
1answer
120 views

LCM of $n$ consecutive natural numbers

Is there an efficient way to calculate the least common multiple of $n$ consecutive natural numbers? For example, suppose $a = 3$ and $b = 5$, and you need to find the LCM of $(3,4,5)$. Then the LCM ...
0
votes
0answers
35 views

Why are the disadvantages of approximation?

When I do 1/3 = 0.33333 but when I do 3*0.33333 then answer is 0.99999, I mean not whole 1 but 0.1 less than 1. What are the drawbacks of this think/rule since it's very basic math. Also why One cant ...
0
votes
1answer
36 views

Prove that $GCD(a,b)=1$ if for all natural numbers $c, a|bc $ then $a|c$.

I'm trying to prove a theorem out of my text: Theorem: Let $a$ and $b$ be natural numbers. Then $GCD(a,b)=1$ if and only if for all natural numbers $c$, if $a|bc$ then $a|c$. I did come across this ...
0
votes
0answers
42 views

If $n \mid a^2 $, what is the largest $m$ for which $m \mid a$?

Given $n$, what is the largest $m$ such that $m \mid a$ for all $a$ with $n \mid a^2$? This is a generalization of if $40|a^2$ prove that $20|a$ when $a$ is an integer where $n=40$ and $m=20$. Here ...
0
votes
0answers
32 views

Is my limited understanding of division and gcd on track?

Hello I am trying to make sense of some beginner theorems and propositions in number theory. I am wanting to also know if what I am saying is valid or just completely wrong. I am wanting to show that ...
1
vote
1answer
20 views

Palindromes and LCM

A palindrome is a number that is the same when read forwards and backwards, such as $43234$. What is the smallest five-digit palindrome that is divisible by $11$? I'm probably terrible at math but ...
2
votes
1answer
46 views

Prove $\gcd\left(\frac{a^m - 1}{a -1},a -1\right) = \gcd(m,a-1)$ [duplicate]

While studying the basics of arithmetic, I've found one problem that I'm not able to solve: Let a and m be two integers, $a \geq 2$ and $ m \geq 1$, with greatest common divisor $1$ ($\gcd(a,m) = ...
1
vote
4answers
77 views

If $3|(a^2 + b^2)$, show that $3|a$ and $3|b$. [duplicate]

I have no idea how to do this problem; please consider helping me: If $3|(a^2 + b^2)$, show that $3|a$ and $3|b$.
0
votes
3answers
43 views

How to prove if $m,n\in \mathbb{Z}$,then $30\mid mn(m^4 -n^4)$

I first thought I'd just have to do cases, i.e. if $m,n$ are even, $m=2l, n=2k$, where $k, l\in \Bbb Z$. But even in this case, alone, I wind up with $4kl(16l - 16k) = 64k(l^2) - 64l(k^2)\dots$ and ...
0
votes
5answers
58 views

How to prove that $7^{15} + 7^{16} + 7^{17} - 1$ is divisible by $10$?

This was a question on my math exam. We weren't able to use calculators so proving by manually calculating the exact value would take too long. In the end I ignored this question to save time but I'm ...
2
votes
4answers
325 views

Proof that $3^c + 7^c - 2$ by induction

I'm trying to prove the for every $c \in \mathbb{N}$, $3^c + 7^c - 2$ is a multiple of $8$. $\mathbb{N} = \{1,2,3,\ldots\}$ Base case: $c = 1$ $(3^1 + 7^1 - 2) = 8$ Base case is true. Now assume ...
1
vote
2answers
78 views

Is 7^2015 + 4^2015 divisible by 17? Explain your reasoning and show your work.

Is $7^{2015} + 4^{2015}$ divisible by 17? Explain your reasoning and show your work. I'm confused on how exactly I would do this. Would I need to use Fermats Theorem?
1
vote
0answers
34 views

Looking applications for these statements involving multiplicative functions and Euler-Fermat theorem

It is well knwon that for positive integers such that $gcd(a,n)=1$, Euler-Fermat Theorem states than $a^{\phi(n)}\equiv 1 \mod n$, where $\phi(n)$ is the Euler totient function counting positive ...
1
vote
1answer
48 views

How to prove: if $a$ is an even integer, $\gcd(a^3 - 1, a + 1) = 1$

I have very little idea of how to tackle this question. I know if $a$ is even, $a = 2L$, for some $L$ in the integer set.
3
votes
4answers
75 views

Prove that $5\mid 8^n - 3^n$ for $n \ge 1$ [duplicate]

I have that $$5\mid 8^n - 3^n$$ The first thing I tried is vía Induction: It is true for $n = 1$, then I have to probe that it's true for $n = n+1$ $$5 \mid 8(8^n -3^n)$$ $$5 \mid 8^{n+1} ...
2
votes
1answer
78 views

Expected number of digits of the smallest prime factor of $1270000^{16384}+1$

The number $N\ :=\ 1270000^{16384}+1$ with $100,005$ digits is given. Given, that $N$ is composite and does not have a prime factor below $2\times 10^{13}$, what is the expected number of digits ...
0
votes
3answers
40 views

Let N be a four digit number, and N' be N with its digits reversed. Prove that N-N' is divisble by 9. Prove that N+N' is divisble by 11.

Let $N$ be a four digit number, and $N'$ be $N$ with its digits reversed. Prove that $N-N'$ is divisible by $9$. Prove that $N+N'$ is divisible by $11$. I let $N=abcd$ and $N'=dcba$ but I dont see ...
-1
votes
2answers
58 views

Prove that if a|b, c|d, then ac|bd [duplicate]

I'm trying to prove it, but I can't find how. If a divides b, and c divides d, then ...
0
votes
5answers
102 views

Prove: If $n^2$ is odd, then $n$ is odd. [duplicate]

$n$ is a natural number. I want to prove that, if the square of $n$ is odd, then $n$ itself is odd. Any hints welcome and preferred. Thank you!
-1
votes
2answers
44 views

Show that if $a, b$, and $c$ are integers with $(a,b)=(a,c)=1$, then $(a,bc)=1$ [duplicate]

Show that if $a, b$, and $c$ are integers with $(a,b)=(a,c)=1$, then $(a,bc)=1$ I don't know exactly that I should use the division algorithm or $(a,b)=d$, $(a/d,b/d)=1$. This is my first time ...
6
votes
1answer
65 views

$\frac{2n\choose n}{n+2}\not\in\mathbb N$ and $n\neq3k+1$ and $n\neq4k+2$

Are there any natural numbers $n\not\equiv1\bmod3$, and $n\not\equiv2\bmod4$, so that $~\dfrac{\displaystyle{2n\choose n}}{n+2}\not\in\mathbb N$ ? Since $C_n=\dfrac{\displaystyle{2n\choose ...
1
vote
1answer
34 views

Divisibility test using perhaps binomial thorem

I have to determine if $17^{21} + 19^{21}$ is divisible by any of the following numbers (a) 36 (b) 19 (c) 17 (d) 21. I am trying to find using binomial expansion but getting stuck up with one or two ...
2
votes
2answers
95 views

Order of group element divides order of finite group

Proving this can be done as follows: consider a finite group G and elements $g_i \in G$ for some integer $i$. Now consider $\langle g_i \rangle = \{g_i^n: n\geq 0\}$, a generator. It can be proved ...
1
vote
1answer
56 views

If $r$ is a nonzero solution $ x^2 + ax + b$, prove that $r | b$

I know that if $r$ is a solution, then there exist two factors of $b$ that when multiplied equal $b$ and that $r$ is one of them. So clearly $r$ divides $b$, but I don't know if there is any other way ...