This tag is for questions about divisibility, that is, determining when one thing is a multiple of another thing.

learn more… | top users | synonyms

0
votes
2answers
46 views

If $m$ is even, and $n$ is odd, does $2(m+n)+2$ have to be divisible by $4?

Can anybody give me an idea of how to solve this? I can't seem to find a counterexample because every integer I choose for m and n is divisible by 4.
1
vote
0answers
86 views

$n^2$ is a multiple of $3$, then $n$ is a multiple of $3$

Consider the following statement: For all $n\in\mathbb{Z}$, if $n^2$ is a multiple of 3, then $n$ is a multiple of $3$. Prove this statement by the contrapositive. So my answer for question 1 ...
1
vote
3answers
29 views

prove polynomial division for any natural number

Show that for any natural numbers $a$, $b$, $c~$ we have $~x^2 + x + 1|x^{3a+2} + x^{3b+1} + x^{3c}$. Any hints on what to use?
0
votes
0answers
29 views

On patterns of divisibility of the sequences of the from $a^n+b$

Let us say that the sequence $a_n$ is partitioned by the subsequences $a_{i_1},a_{i_2},...a_{i_m}$ if for every $n_0 \in \mathbb N$ there is $i_j \in \{i_1,i_2,...,i_m\}$ such that ...
-1
votes
2answers
32 views

Polynomial Divisibility Proof Problem [closed]

Given $(x^2+x+1)|(f_1(x^3)+xf_2(x^3))$, show that $(x-1)|f_1(x)$ and $(x-1)|f_2(x)$. Thanks!
-1
votes
1answer
25 views

How to determine whether numbers are congruent modulo n [closed]

I have a midterm coming up this Monday so I am preparing for the test. There's one topic that I need a better explaination of this question Determine whether numbers are congruent modulo n Can ...
-1
votes
1answer
28 views

Prove if a | b, then a | bc for all integers c ,true

Please prove that ) if a | b, then a | bc for all integers c; my solution: b= a x j c= a x d and I don't know what do I have to do next or how can I have a good proof.
3
votes
4answers
87 views

If $3^2$ divides $2^n-1$, then $n$ must be divisible by $6$

I was riffling through some old posts (see the link at the bottom of this post) in which it was given as a fact that if $3^2$ divides $2^n-1$, then $n$ is divisible by $6$. It was given in the post ...
2
votes
3answers
40 views

Prove that ∀a, b, u, v ∈ Z − {0} ua + vb = 1 → gcd(a, b) = 1

How can I prove this statement: $\forall a,b,u,v \in \mathbb{Z} - \big\{{0\big\}}\hspace{0.7em}ua+vb=1 \rightarrow \gcd(a,b)=1$ I don't even really know how to start off. Probably with Euclid's ...
2
votes
0answers
40 views

Determine All Divisors of $f(x)=x^n\in F[x]$

Carefully determine all divisors of $f(x)$ where $$ f(x)=x^n\in F[x]$$ note that $F[x]$ is a Field So, $$ \underbrace{x^0\mid x^n,\ x^1\mid x^n,\dots,\ x^n\mid x^n}_{n+1}$$ making $n+1$ divisors. ...
0
votes
0answers
16 views

Characteristics of divisibility in the system with base 7

I have a problem . What are the characteristics of divisibility of numbers in the system on the basis of 7 Well , I have a number of system 7 and wants to check whether the shares divisible by 6 , 8, ...
1
vote
2answers
33 views

Finding the digits of the number $789ABC$

Find the digits of the number $$789ABC$$ where the resulting number is divisible by $7,8$ and $9$. However, A,B, and C cannot be $7,8$ or $9$ Here are some information i found out: I know $ABC$ ...
2
votes
0answers
22 views

Divisibility of factorials

There are two numbers, $n$ and $p$, with prime $p$ and $n < p$. One is to calculate $n! \bmod p$. Is there any chance of doing this without explicitly determining $n!$ ? I already know that with ...
10
votes
2answers
224 views

What is your idea about this conjecture?

I conjecture that in a consecutive sequence of $n$ natural numbers all greater than $n$, there exists at least one number which is not divisible by any prime number less than or equal to $n/2$. Can ...
11
votes
3answers
4k views

Prove that 17 divides 1111111111111111 (16 1's) and doesn't divide 11111111

I need to prove that $17$ divides $\underbrace{1111111111111111}_{\text{16 1's}}$ and doesn't divide $\underbrace{11111111}_{\text{8 1's}}$ by using congruence. I know that ...
2
votes
5answers
81 views

Inductive proof that $n(n-1)(n+1)$ is divisible by $6$

I am trying to prove that $n(n-1)(n+1)$ is divisible by $6$ for all $n$ in $\mathbb{N}$. My attempt: The result certainly holds for $n=0$. Suppose now that $n > 0$. Assume that $P(k)$ is true for ...
6
votes
0answers
58 views

Divisibility sequence resulting in limit with pi

Consider the following sequence of operations : Start with a natural number $n$ and then round it up to the closest multiple of $n-1$ .Then round up this new number to the closest multiple of ...
0
votes
2answers
36 views

4 Divides x Proofs of conjectures

Hi there I'm working on a set of problems and I'm having some difficulty proving and disproving these examples. I know that #1 is essentially (There exists K where [x=4k]) I'm lost after that. I'm not ...
0
votes
1answer
59 views

If dividing $n$ by $m$ yields remainder $r$, then dividing $-n$ by $m$ yields remainder $-r$

Let m and n be positive integers and let r be the nonzero remainder when n is divided by m. Prove that when -n is divided by m, the remainder is m - r So far I've tried I get n = qm + r and -n = q'm ...
3
votes
2answers
61 views

Is there a mathematical definition for the “divisibility” of rational numbers?

The term divisibility usually refers to integer numbers only. I want to define the divisibility of a rational number $q$ by an integer number $z$ as follows: $q$ is divisible by $z$ if and only if ...
1
vote
1answer
35 views

Simple Division Problem

I have the equation: $$(1-\frac{1}{2^2})...(1-\frac{1}{n^2}) = \frac{n+1}{2n}$$ for n ≥ 2 Trying to prove by induction and I get the following equation. $$\frac{k+1}{2k} + \frac{k(k+2)}{(k+1)^2} = ...
1
vote
1answer
28 views

Greatest common divisor of linear combination of two comprime numbers

How to calculate $\gcd(2n+3m,n-m)$ if $\gcd(n,m)=1$ $\gcd(2n+3m,n-m)= \gcd(2n+3m+ 3(n-m),n-m)=\gcd(5n,n-m)= $ and i don't know. Plase help me
-2
votes
1answer
29 views

Divisibility criterion for 11

What is a quick way to prove using induction the following fact: "A number is a multiple of 11 if and only if the sum of its even-placed digits minus the sum of its odd-placed digits is also a ...
1
vote
1answer
31 views

Prove that 1 less than the number of equivalence classes divides $p-1$ where $p$ is prime

I am faced with the following problem: Let $p$ be a prime number and $\gcd(p,n)=1$. Define an equivalence relation on $\mathbb{Z}_{p}$ as follows: $x \sim y$ iff $n^{r}x = n^{t}y$ for some $r,t ...
1
vote
1answer
41 views

Can I mix direct proof with inductive proof?

Let's say I want to prove with induction that $3|n$ implies $3|n^2$ Let $n = 3k$. The statement is true for $k=1$ since $3|3$ and $3|9$ We assume the statement is true for $k=z$ so $3|3z$ ...
2
votes
1answer
40 views

Can integers be divisible by real numbers?

I have searched for many definitions of divisibility and they all seem to go like this: Let $a, b \in \mathbb{Z}$ then $b$ is divisible by $a$ if there exists $c \in \mathbb{Z} : b = ac$. Is ...
1
vote
3answers
58 views

For which $n ≥ 0$ is $2^n + 2 · 3^n$ divisible by $8$?

Stuck on this problem for some time: For which $n ≥ 0$ is $2^n + 2 · 3^n$ divisible by $8$? I've reached the conclusion that $n = 1$ is the only solution to the question at hand, but I cant quite ...
1
vote
2answers
38 views

4 variables how many combos of 3 can you make

If you have 4 variables A, B, C, D How many combos can you make that use 3 of the variable and are unique (order matters), so I mean A,B,C and B,A,C only counts ...
1
vote
2answers
38 views

Finding how many numbers are divisible by a prime number

I'm trying to figure out how I can find out how many numbers are divisible by a certain prime (eg 3) in a certain range, eg 0-10000. I think it has something to do with permutations, but I'm not ...
1
vote
5answers
91 views

Mathematical Induction Divisibility Problem

Prove that if $n \ge 1$ is a positive integer, then $13^n − 6^n$ is divisible by $7$. In proving the $n = k+1$ case, I get to $133k + 6^k\cdot13 - 6\cdot13^k = 7M$, where $M$ is a positive integer. ...
3
votes
2answers
44 views

Number of ordered pairs $(x, y)$ such that $0 \leq x, y\leq 18$ and $3x+4y+5$ is divisible by $19$

The problem would have been much simpler if there was no constant term, (like $3x+4y$ divisible by 19) because then all the solutions could have been generated from just the solution to $3x+4y=19$. ...
0
votes
2answers
40 views

A simple question about divisibility: If $n$ divides the product of coprime numbers…

This is quite basic, but I'm no good at this stuff, and I've basically just been sitting her trying to find counterexamples... If $n$ divides $jk$, where $gcd(j,k)=1$, must $n$ divide $j$ and $k$? ...
14
votes
6answers
3k views

Is an arbitrary number of the form xyzxyz divisible by 7, 11, 13?

So I was given this question Choose any 3-digit number xyz and write it after itself as follows: xyzxyz. Check whether it is divisible by 7,11, 13. Is an arbitrary number of the form xyzxyz ...
0
votes
2answers
41 views

How to prove that $4n^2+4n+8$ is even?

I'm trying to prove that $4n^2+4n+8$ is even. I tried dividing the polynomial by $2n$ to get a remainder of $8$. Is this correct? how do I proceed ?
0
votes
3answers
43 views

Why are every number (integer) exactly divisible by 5 in decimal number system but not in binary number system?

I have wondered during the number system classes in computer science that if 1/5 in decimal number system results in 0.2 why ...
2
votes
1answer
23 views

Prove $ax=ay \pmod {p^2}$ implies $x=y \pmod {p^2}$

Let $p$ be a prime and $a$ an integer not divisible by $p$. Prove $ax=ay \pmod {p^2}$ implies $x=y \pmod {p^2}$ $p^2$ divides $a(x-y)$ implies $p$ divides $a(x-y)$. $p$ does not divide $a$ implies ...
1
vote
1answer
25 views

Greatest common divisor of 2n+1 and 9n+4

Calculate $GCD(2n+1,9n+4)$ and $GCD(2n-1,9n+4)$ $$GCD(2n+1,9n+4)=GCD(2n+1,9n+4-4 \cdot (2n+1))=GCD(2n+1,n)= GCD(n,1)=1$$ How to calculate $GCD(2n-1,9n+4)$
3
votes
0answers
57 views

An upper bound for the number of answers of this equation

Let $n$ be a natural number and $p$ a prime number less than or equal to $n$. $$\begin{align} n^2 + 2n &\equiv a \pmod p\\ n^2 + 1 &\equiv b \pmod p \end{align}$$ If $a \lt b$, $p$ is ...
0
votes
1answer
22 views

Finding number of integers divisible by 2, 3 or 4 using inclusion-exclusion principle.

I want to find number of integers from 1 to 19 (both included) which are divisible by 2 or 3 or 4. Lets denote it by N. So counting and enumerating them gives N = 12. Integers are 2, 3, 4, 6, 8, 9, ...
0
votes
1answer
37 views

Find all non-negative integers $n$ satisfying $2^{n}\equiv n^{2} mod\, 5$

I'm trying to find all non-negative integers $n$ satisfying $2^{n}\equiv n^{2}\pmod{5}$. So far, all the progress I've made is figuring out that $n^{2} mod \, 5$ for $n=1$ to $5$ has the pattern ...
0
votes
2answers
46 views

Division theorem for polynomials with integer coefficients

I can see that the Division Theorem holds for polynomials in $\mathbb{Q}[x]$, but does not necessarily hold for polynomials in $\mathbb{Z}[x]$, e.g. Let $f=x^2+3x$ and $g=5x+2$. Then the Division ...
0
votes
1answer
50 views

Better proof of $X^5=Y^2+4$ has no solutions in $\bf Z$?

Consider: $X^5=Y^2+4$ $X,Y \in \bf Z$. If $11 \not | X \rightarrow X^{10}-1\equiv 0 \pmod {11}\rightarrow (X^5-1)(X^5+1)\equiv 0 \pmod {11} $. From here we do a remainder table for all numbers and ...
1
vote
1answer
24 views

How do i work out the added 20% from the final result

According to my employee contract because I am casual I am being paid with an extra 20% loading making my total being $22/h. I wanted to work out how much I would normally have been paid if I wasn't ...
3
votes
2answers
119 views

Does $\gcd(a,bc)$ divides $\gcd(a, b)\gcd(a, c)$?

I want to prove that $\gcd(a,bc)$ divides $\gcd(a,b)\gcd(a,c)$ but I can't succeed. I tried to go with $\gcd(a,b) = sa+tb$ and it didn't work, tried to use the fact that $\gcd(a,b)$ and $\gcd ...
1
vote
2answers
42 views

Does the LCM of $ax$ and $bx$ equal $\operatorname{lcm}(a,b)\cdot x$?

Let $a,b,x \in Z^+$. Prove that $\operatorname{lcm}(ax,bx) = \operatorname{lcm}(a,b)\cdot x$. Here are my thoughts: Let $d = \operatorname{lcm}(ax, bx)$. By definition $ax|d$ and $bx|d$. Now it can ...
1
vote
1answer
53 views

Prove that if $m\mid (a^2 -1)$ then $m\mid (a^4 -1)$

I have been stuck on this question for quite some time, I have tried several methods but to no avail. I attempted to use prime factorization but I couldn't really see where to go with it.
0
votes
0answers
29 views

On $\sum_{k\nmid n}k$, where the sum is over the integers $1\leq k\leq n$ such that $k\nmid n$, and perfect numbers

If we define the arithmetic function $\delta(n)$ as the sum of integers $1\leq k\leq n$ such that $k\nmid n$, we have by Gauss statement $\sum_{k=1}^n k=n(n+1)/2$, that ...
0
votes
4answers
53 views

Showing $n^3 - n$ is divisible by $6$ [duplicate]

How would you show that $n^3-n$ is divisible by $6$, when $n=k+1$ ?
-1
votes
1answer
74 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$