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

learn more… | top users | synonyms

-2
votes
3answers
106 views

Division problems

I came across these problems : 1) Find the lowest natural number $k$ that satisfies the condition : $ 7 \mid A$ , where $A = 194^{19} + 125^{14} + k $ 2) Find the different prime numbers ...
12
votes
2answers
491 views

Show divisibility by 7

I was stuck at this question: Suppose $a^2+b^2=c^2$ for $a,b,c \in \mathbb Z$, and neither $a$ nor $b$ is a multiple of 7. Show that $a^2-b^2$ is a multiple of 7 I tried to write $b^2$ as ...
1
vote
2answers
193 views

Probability of getting a five digit number divisible by 5 but with no two consecutive digits identical

A five digit number is written down at random. What is the probability of getting a number that is both divisible by 5 and doesn't have any 2 consecutive digits identical? I tried to analyse the ...
11
votes
0answers
256 views

Dividing the whole into a minimal amount of parts to equally distribute it between different groups.

Suppose we have a finite amount of numbers $x_1, x_2, ..., x_n$ ($x_i\in\mathbb{N}$) and an object that should be divided into parts in such a way that it can be without further dividing distributed ...
5
votes
3answers
197 views

Is $a=\frac{1992!-1}{3449\times 8627}$ a prime number?

Is $a=\dfrac{1992!-1}{3449\times 8627}$ a prime number ? This is a natural follow-up to that recent MSE question We know that $a$ has $5702$ digits and no prime divisor $<10^6$.
1
vote
2answers
40 views

Explain 'expressing a number using its digits'

While studying divisibilty and prime numbers in my maths book (IB Mathematic Higher Level Option 10: Discrete Mathematics), I came across an explanation of a way to '[express] a number using its ...
-2
votes
1answer
48 views

How would you divide a polynomial by another polynomial whose power is greater than its nominator? [closed]

I have a polynomial which is: $$\frac{(x^3-4x)}{(4x^2-4x+1)} = -10$$ Is there a way to do this? I have thought about doing long division which was not helpful...
3
votes
1answer
146 views

Prove that $n \in \mathbb{Z}^\star \Leftrightarrow n \mid 1$ and $n-1 \mid 1$ or $n+1 \mid 1$, and $(x-1)/(t-1) \equiv n \pmod {t-1}$

I want to prove the following lemma: Let $F[t,t^{-1}]$ be the ring of the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$ and assume that the characteristic of $F$ is zero. ...
1
vote
1answer
53 views

Least Common Multiple and Greatest Common Divisor

Prove that if $\mathop{\mathrm{lcm}}( a, b) + \gcd(a, b) = a+b$, $a$ divides $b$ or $b$ divides $a$. This problem seemed simple at first, however I cannot figure out a way to prove this. If I assume ...
0
votes
3answers
51 views

proof for divisibility

Prove without the use of congruences that $341$ divides $2^{340} - 1$. This was a question I found in a book right after which Fermat's little theorem is discussed. I tried using it for the proof but ...
0
votes
0answers
21 views

Divisibility in $\mathbb C[t]$

I am looking for all the polynomials $P,Q,R\in\mathbb C[t]$ such that $121P^2+614PQ+841Q^2-R^2$ divides $11P+29Q-R$. I remarked that $$121P^2+614PQ+841Q^2=(11P+29Q)^2-24PQ.$$ So, ...
2
votes
1answer
162 views

Why is the sum of any ten consecutive Fibonacci numbers always divisible by $11$?

I was wondering if anyone has any insights regarding the fact that the sum of any $a_1, \dots, a_{10}$ consecutive Fibonacci numbers is divisible by $11$ (and furthermore equals to $a_7*11$). What can ...
1
vote
0answers
39 views

Is this :$\sum_{n=1}^{\infty} \frac{\sigma_{k}(n)}{n!} $ irrational series for every natural number $k$?

Is this: $$\sum_{n=1}^{\infty} \frac{\sigma_{k}(n)}{n!} $$ irrational series for every natural number $k$? Where : $\sigma_{k}(n)=\sigma(\sigma(\sigma(\dots n)))$ is the $k$-th iterate of the sum of ...
1
vote
2answers
33 views

$k | x^{k} - x,$ for $k, x \in \mathbb{Z}$?

I seem to have found that: $$k | x^{k} - x, \ \text{for} \ k, x \in \mathbb{Z}.$$ I have tried it with a few values, and it seems to be true. I am sure that this has been discovered before.
3
votes
4answers
63 views

How do I show that we can't write $N=114^n-1$ as sum of $3$ squares for all natural number $n>2$?

I run some computations in wolfram alpha, I see that we can't write :$$N=114^n-1$$ as sum of $3$ squares, then Hop someone who can show me how I do prove that we can't write $N=114^n-1$ as sum of $3$ ...
0
votes
0answers
47 views

Divisibility Question [duplicate]

If $(ab+1)$ divides $(a^2+b^2)$ then prove that $(a^2+b^2)$ when divided by $(ab+1)$ gives a square of an integer.
4
votes
5answers
134 views

Show that $4$ does not divide $x^3-2$

Show that $4$ does not divide $x^3-2$ is what I need to prove. I think I should put $4k$ is $x^3-2$ and then contradict it somehow. Alternatively is to factor it out as $x^3$ is $x(x+2)(x-2)$ but I ...
2
votes
2answers
121 views

Prove that rational numbers $a,b$ are integers if $a+b$ and $ab$ are integers

I have been trying to prove this via divisibility, assuming that $a=\frac{n}{m}$ and $b=\frac{r}{q}$ for some $n,m,r,q$ in Ints($m$,$q$ not $0$), but I'm completely stuck here. Any help?
0
votes
1answer
38 views

How do I show that :$\sigma({p^m})$ is divisible by $4$ if $m=4k+1$ , and $k$ is an integer number?

How do i show this if it's not an open problem :$\sigma({p^m})$ is divisible by $4$ if $m=4k+1$ , and $k$ is an integer number and p is prime number. and $\sigma({p^m})$ is sum divisors of $p^m$ ...
2
votes
2answers
80 views

When does :$\sigma(\sigma(2n))=\sigma(\sigma(n))$ and $\sigma(n)$ is sum divisors of the positive integer $n$?

Is there someone who can show me When does: $$\sigma(\sigma(2n))=\sigma(\sigma(n))$$ where : $\sigma(n)$ denote the sum divisors of the positive integer $n$ ? Note (1) : I accrossed this problem when ...
35
votes
3answers
786 views

Prove that there exist infinitely many integers $(n^{2015}+1)\mid n!$

I conjecture that there exist infinitely many integers $n$ such that $$(n^{2015}+1)\mid n!.$$ I have seen a simpler problem that there exist infinitely many integers $n$ such that $(n^2+1)\mid ...
0
votes
1answer
83 views

Prove: If $d|a$ and $d|b$ then $d^2|ab$

Prove: If $d|a$ and $d|b$ then $d^2|ab$ All I have $ab = kd^2$, $k$ some integer. I'm stuck and hoping someone could walk me through this!
-5
votes
1answer
51 views

Proof - a | b and b | a then a = b [closed]

For all integers a and b, if a | b and b | a, a = b. Can something think of a proof? I have done this: Proof: Suppose m and n are integers such that m|n and n|m, but n ≠ m. Let m = 1 and n = ...
0
votes
2answers
60 views

How do I show $1$ is not a trivial odd perfect number?

This question related to my this question in MO ,some comments stated that the integer $1$ is trivial answer for this question ,but here i'm very confused when we say that the sum divisors of $1$ is ...
3
votes
1answer
93 views

Numbers divisible by all of their digits: Why don't 4's show up in 6- or 7- digit numbers?

For reasons I'll explain below the question if you're interested, I stumbled across a peculiar phenomenon involving numbers divisible by their digits. I'm concerned with numbers that are divisible by ...
0
votes
1answer
31 views

Determine overall ratio from individual ratios

I have a set of statistics that I need to find the overall ratio to. This example will work with only two items so I'll write them down: ...
0
votes
2answers
65 views

Why is it true that if $ax+by=d$ then $\gcd(a,b)$ divides $d$?

Can someone help me understand this statement: If $ax+by=d$ then $\gcd(a,b)$ divides $d$. Bezout's identity states that: the greatest common divisor $d$ is the smallest positive integer that ...
1
vote
1answer
88 views

How to use the division algorithm to prove these form of integers?

I have in my notes the form of the integers as: Now, I know that I have to use the division algorithim to prove the first form, and I can do this, but in the second form of an integer $4k$ isn't the ...
2
votes
5answers
118 views

Proving $n^3 + 3n^2 +2n$ is divisible by $6$

The full question is: Factorise $n^3 + 3n^2 + 2n$. Hence prove that when $n$ is a positive integer, $n^3 + 3n^2 + 2n$ is always divisible by $6$. So i factorised and got $n(n+1)(n+2)$ which i think ...
0
votes
1answer
26 views

The lowest number that is divisible by a and b

I have the numbers $a = 120, b = 144$. So if I prime them I get $120 = 5\times3\times2\times2\times2$ and $b = 144 = 2\times3\times3\times2\times2\times2$. I am looking for the lowest number that is ...
3
votes
3answers
58 views

Is this formula true for $n\geq 1$:$4^n+2 \equiv 0 \mod 6 $?

Is this formula true for $n\geq 1$:$$4^n+2 \equiv 0 \mod 6 $$. Note :I have tried for some values of $n\geq 1$ i think it's true such that :I used the sum digits of this number:$N=114$,$$1+1+4\equiv ...
2
votes
1answer
25 views

A question about the divisibility of certain polynomial sequences.

$2n+1=(n+1)^2-(n)^2$ . Therefore $(n+1)^2-n^2$ never divides $2$ for any integers.Can we make a similar statement for $(n+1)^x-n^x=a_n$ ... And if we can, can we combine polynomials to give us a ...
2
votes
2answers
167 views

Divisibility question

Prove: (A) sum of two squares of two odd integers cannot be a perfect square (B) the product of four consecutive integers is $1$ less than a perfect square For (A) I let the two odd integers ...
1
vote
5answers
55 views

Divisibility theory help

If $a$ is odd, show that $32 \mid (a^2 + 3)(a^2 + 7)$ Since $a$ is odd, I let $a = 2b + 1$ and did the expansion to get $16\mid [(b^2 + b +1)(b^2 + b + 2)]$, but I was unable to continue from ...
3
votes
1answer
78 views

Frazzle game question

In $7^{th}$ grade, in order to learn divisibility, memory, and focus, my math teacher had my pre-algebra class play a game called Frazzle. To play the game Frazzle, each person went around the room ...
1
vote
0answers
55 views

Probability number is divisible by half the square of a prime?

Let $p$ be a prime. What is the probability that a number of the form $\left \lceil \frac{p^2}{2} \right \rceil$ divides a random positive integer $n$. I have a solution that involves the Riemann-Zeta ...
0
votes
0answers
39 views

Rabin's cryptography - when the message $M$ isn't coprime to $n = pq$

Say the message $M$ is a product of one of the primes $p$ or $q$, won't the $gcd$ of $M$ and $n$ (the public encryption key) give me $p$ or $q$? say $p = 11$ $q=19$ $n=11*19=209$ and $M=33$. ...
1
vote
4answers
98 views

How do I show that:if$p$ is prime $>5$ then $p^4-20p^2+19$ is always divisible by $180$.?

Is there someone who can show me How do i show that :If $p$ is a prime number greater than $5$ then : $$p^4-20p^2+19$$ is always divisible by $180$. Note : i think should factor $p^4-20p^2+19=$ ...
2
votes
2answers
355 views

Fermat's little theorem

This is a very interesting word problem that I came across in an old textbook of mine. So I mused over this problem for a while and tried to look at the different ways to approach it but unfortunately ...
3
votes
4answers
66 views

Proving that $i! \mid (p-1)\cdot(p-2)\cdots(p-i+1)$ for $i < p$

Started solving this problem: $$ (a+b)^p \equiv a^p+b^p \pmod{p}$$ where $p\in\mathbb{P}$, $a,b\in\mathbb{Z} $ After a few implications I arrived to this $$ i! \mid ...
0
votes
3answers
71 views

Are there any divisibility rules using 7? [duplicate]

Divisibility rules of 1,2,3,4,5,6,8,9 are first or second grade math. Are there any divisibility rules for numbers with factors including 7. I noticed that the digits of 7x starting with x=1 to x=5 ...
4
votes
2answers
34 views

GCD of many numbers divisible by another number

$a$ is an integer such that: $$a \mid \gcd(b_1,b_2,\ldots,b_z)$$ and $z$ can be very large. Does the GCD approach $a$ as $z$ grows? If yes, what is the relation between $z$ and $a$? Thanks...
1
vote
1answer
67 views

Can we always write $gcd(x,y)$ as $ax+by$ in UFD?

Let $R$ be a commutative ring with unity. Now assume that $R$ is Unique Factorization Domain, but not necessarily Principal Ideal Domain. Question: Let $x,y\in R$ be such that their GCD exists in ...
2
votes
2answers
82 views

Number Theory- Mathematical Proof

I am trying to prove a theorem in my textbook using another theorem. What I need to show that if a,b, and c are positive integers, show that the least positive integer linear combination of a and b ...
2
votes
1answer
39 views

Is there a way to figure out the number of possible combinations in a given total using specific units

I'm not professional mathematician but I do love a math problem - this one, however has me stumped. I'm a UX Designer trying to figure out some guidelines for using tables in a page layout. The thing ...
1
vote
0answers
53 views

Given a number $N$ and a prime $P$, how many numbers $\leq N$ are divisable by P but not by any smaller primes?

The following Math Exchange question deals with a similar problem: not divisible by 2,3 or 5 but divisible by 7 However, the answers given become infeasible quite quickly because the amount of ...
1
vote
1answer
99 views

how can one show that if $m$ and $n$ are co-prime, then $U_n$ and $U_m$ are also co-prime?

Given that $$U_n=\underbrace{1\cdots1}_{n\text{ times}}$$ and $n >2$, how can one show that if $m$ and $n$ are co-prime, then $U_n$ and $U_m$ are also co-prime? Because $U_m= ...
0
votes
3answers
57 views

Find remainder of $\frac{17^{235}}{ 23}$

I need to find remainder of $\frac{17^{235}}{ 23}$. This is supposed to be solved using the following method: $\varphi(23) = 22$ ${17}^{235} = (({17}^{22})^{10})\cdot {17}^{15}$ ${17}^{22}\equiv 1 ...
0
votes
1answer
100 views

Division with dividend less than divisor

Let $a\geq b$. We define the division of $a$ by $b$ to be, $$a=bq+r,$$ where $q,r$ are integers and $0\leq r<b$. How we divide $a$ by $b$ when $a<b$.?
0
votes
0answers
25 views

Given An initial point and final point ,How to determine the number of Co-Ordinates(x,y) such that both x and y are integral?

I have thought a lot about it and still no clue. I thought of visualising the initial point and the end point in the form of a Grid. But ,soon I was over with my resources. Problem: Given an initial ...