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
2answers
49 views

Find all numbers of form $10^k+1$ divisible by $49$

Basically, I've tried to take mods, and it hasn't been very successful. Also, if it helps, I noticed that the sequence can be recursively written as $a_{n+1}=10a_n-9$, starting with $a_1=11$.
0
votes
0answers
29 views

Determine when a prime divides this

Let $x$ and $y$ be integers, and consider the expressions $A=192x+a$ and $B=192y+b$, where $a,b$ are nonnegative mod $192$ residues (so $a,b\in \{0,1,2,...,191\}$). For which ordered pairs $(a,b)$ ...
0
votes
1answer
51 views

Principal Ideal Ring and ID

In definition of PID, if we take ring instead of ID call it PIR. I add one more condition: all generators of an ideal are associate to each other. Would it imply PIR with this condition is PID? ...
0
votes
1answer
102 views

prime implies irreducible

In unique factorization ring with unity(I am not considering commutativity and zero divisor in definition of UFD) irreducible implies prime. And it was proved in ring with unity without zero ...
3
votes
2answers
36 views

What is sum of totatives of n(natural numbers $ \lt n$ coprime to $n$ )?

Same question as in title: What is sum of natural numbers that are coprime to $n$ and are $ \lt n$ ? I know how to count number of them using Euler's function, but how to calculate sum?
0
votes
1answer
54 views

UFD, prime and Irreducible

I am taking following definitions and calling algebraic structure U1 and U2 definition as: U1 is A ring R with unity and properties properties Every element of R is neither 0 nor a unit can be ...
0
votes
1answer
80 views

Prime element in ring without unity

Definitions of prime element: $(1)$ We say $p$ is prime if $p|ab$ it implies $p|a$ or $p|b$ (I don't need definition of unity here) $(2)$ We say $p$ is prime if $p=ab$ it implies $p|a$ or $p|b$ (I ...
3
votes
2answers
66 views

How to find a Fibonacci number that is divisible by $x$?

I'm looking for an algorithm that is better than just checking every number in the Fib Sequence for divisibility. Example: Find the first Fib number that is divisible by $x=223321$, with no ...
3
votes
1answer
60 views

When is $(12x+5)/(12y+2)$ not in lowest terms?

I am struggling to solve this problem and would appreciate any help: When is $\frac{12x+5}{12y+2}$ NOT in lowest terms? (x,y are nonnegative integers) I have found that it is not in lowest terms for ...
1
vote
2answers
44 views

Linear congruence fill in the missing step?

Currently working on this problem and I'm having trouble seeing how it goes from one line to the next. $45x \equiv 63\mod 11$ goes to $x \equiv 8\mod 11$ Any help would be awesome thanks. ...
1
vote
3answers
59 views

If p is an odd prime, prove that $a^{2p-1} \equiv a \pmod{ 2p}$

Let $m = 2p$ If p is an odd prime, prove that $a^{2p - 1} \equiv a \pmod {2p} \iff a^{m - 1} \equiv a \pmod m$. I have no idea on how to start. I was trying to find a form such that $a^{m - 2} ...
0
votes
1answer
26 views

Does $ p|(2^{2kq}-2^{kq}+1)$ where $p=1+k\cdot q$ ? I'm stuck…

Does $ p|(2^{2kq}-2^{kq}+1)$ ,$p=1+k\cdot q$,where $p,q$ are prime ? From Fermat's little theorem; $(2^{2kq}-2^{kq}+1)$ mod $q\equiv (2^{2k}-2^{k}+1)$ This is where I'm stuck, please help. Thank ...
4
votes
1answer
75 views

Prove that $(z^3-z)(z+2)$ is divisible by $12$ for all integers $z$

I am a student and this question is part of my homework. May you tell me if my proof is correct? Thanks for your help! Prove that $(z^3-z)(z+2)$ is divisible by $12$ for all integers $z$. ...
0
votes
1answer
28 views

Number theory hcf confusion

I need to show 11|(100a+b) if and only if 11|(a+b). The solution: 11|(100a+b) iff 11|(100a+b-99a) so obviously 11|(a+b) and we have the solution as easily as that. However I cannot see why this is ...
0
votes
0answers
21 views

Form of Divisors of Proth numbers

Proth number is a number of the form : $z⋅2^k+1$ where z is an odd positive integer and k is a positive integer such that : $2^k>z$ Is there a form for divisors of Proth Numbers? (Like Mersenne ...
3
votes
3answers
88 views

Let $a,b$ be positive integers such that $a\mid b^2 , b^2\mid a^3 , a^3\mid b^4 \ldots$ so on , then $a=b$?

Let $a,b$ be positive integers such that $a\mid b^2 , b^2\mid a^3 , a^3\mid b^4 \ldots$ that is $a^{2n-1}\mid b^{2n} ; b^{2n}\mid a^{2n+1} , \forall n \in \mathbb Z^+$ , then is it true that $a=b$ ?
1
vote
1answer
32 views

$n,a,b \mathbb \in \mathbb Z^+$ , such that $n\mid a^n-b^n$ ; to show $n\mid \frac {a^n-b^n}{a-b}$ [duplicate]

Let $n,a,b \in \mathbb Z^+$ be such that $n\mid a^n-b^n$ , then how to prove that $n\mid {\dfrac {a^n-b^n}{a-b}}$ ? My try : $d=\gcd(n,a-b),$ so $d \mid{\dfrac {a^n-b^n}{a-b}}.$ Also $\,n ...
2
votes
3answers
60 views

Number Theory Simple Proof Confusion

Suppose that c|ab and (b, c) = 1. Then c|a Proof (ab, ac) =|a|(b, c) = |a|. But by hypothesis, one has c|ab, which implies that c|(ab, ac). We thus conclude that c|a. And the proof is complete. I am ...
0
votes
1answer
36 views

How does author reach step of $sa + tm \equiv 1 \pmod m$?

This is a proof of a theorem from my book, Discrete Mathematics and its Applications Theorem 1 If $a$ and $m$ are relatively prime integers and $m>1$, then an inverse of $a$ modulo $m$ ...
0
votes
1answer
32 views

To prove for every integer $k >1 $ , $2+2^k \choose r$ is even for all $2 < r \le n=1+2^{k-1}$ , without Lucas' theorem

Can we prove by induction that for every integer $k >1 $ , $2+2^k \choose r$ is even for all $2 < r \le n=1+2^{k-1}$ ? Or by some divisibility properties of Binomial co-efficients ? I wanted to ...
3
votes
4answers
48 views

Prove that if $na=mb$ and $(a,b)=1$, then $m=a$ and $n=b$.

I'm sorry but I'm having a massive brain fart. I'm trying to show that if $na=mb$ and $(a,b)=1$, with $a,b,n,m \in \mathbb{N}$ of course, then $m=a$ and $n=b$. Moving to $\mathbb{Q}_+$, we note that ...
0
votes
1answer
49 views

Formula of MIPS (million instructions per second)

Could you please help me to understand the mathematics behind MIPS rating formula? The performance of a CPU (processor) can be measured in MIPS. The formula for MIPS is: $$MIPS = \frac{Instruction \ ...
5
votes
3answers
106 views

Solve: $ab+bc+ca\mid (a+b+c)^2$

I couldn't make any progress on this problem, can anyone help? I found it's the same as: Find all integers $a,b,c$ such that $ab+bc+ca$ divides $a^2+b^2+c^2$. I found a solution $a=-b=1$, and $c$ ...
1
vote
1answer
15 views

If $n \in \mathbb Z^+$ , $a,b$ are integers such that $d=g.c.d.(a-b,n)$ , then $d^2|a^n-b^n$ ?

If $n \in \mathbb Z^+$ , $a,b$ are integers such that $d=g.c.d.(a-b,n)$ , then is it true that $d^2|a^n-b^n$ ?
0
votes
1answer
15 views

Find $a+b$ for $a, b$ such that $(x+1)^{n}(x^{2}+ax+b) \equiv 2^{n}(x-1) \mod (x-1)^{2}$

Since $2^{n} = \sum_{0}^{n}\binom{n}{k},$ we have from the given congruence the congruence $$\sum_{0}^{n}\binom{n}{k}(x^{k+2} + ax^{k+1} + bx^{k} - x +1) \equiv 0 \mod (x-1)^{2}.$$ The given answer ...
-1
votes
2answers
89 views

Proof that if x is prime, then x+7 is composite. [closed]

Proof that if x is prime, then x+7 is composite. I do not know how to prove it. Can anyone help me to solve it? Thx
11
votes
2answers
222 views

Show that $A[X]/(aX+b)$ is an integral domain

Let $A$ be an integral domain, $a$ and $b \in A-\{0\}$, and let $B = A[X]/(aX+b)$. Show that, if $Aa \cap Ab=Aab$, then $B$ is an integral domain. My attempt at proof (following a hint). Denote ...
-2
votes
2answers
49 views

If $a,b,c\neq0$, prove that $ac\mid bc \iff a\mid b$ [closed]

How can I prove this question? If $a,b,c\neq0$, prove that $ac\mid bc \iff a\mid b$ Please help me
1
vote
2answers
51 views

If $n^m\mid m^n$ and $k^n\mid n^k$, prove $k^m\mid m^k$, $m,n,k\in \mathbb{Z}^+$

If $n^m\mid m^n$ and $k^n\mid n^k$, then $k^m\mid m^k$, $m,n,k\in \mathbb{Z}^+$ Aside from the definition of divisibility, can someone suggest theorems/facts that might be useful in proving this ...
0
votes
4answers
77 views

How can I show that $(x-1)(x^2-1)$ divides the polynomial $(x^n-1)(x^{n+1}-1)$? [closed]

How can I show that $(x-1)(x^2-1)$ divides the polynomial $(x^n-1)(x^{n+1}-1)$?
3
votes
2answers
69 views

$f,g,h$ are polynomials. Show that…

Let $f,g$ and $h$ be polynomials. Show that $\gcd(f,g,h)=\gcd(\gcd(f,g),h)$. I was thinking of signing $\gcd(f,g)=d$ and then write it by using Euclid's algorithm, but I couldn't get anything proper. ...
4
votes
1answer
48 views

To prove ${2p - 1 \choose p } \equiv 1 \pmod{p^2}$ without using Wolstenholme's theorem

How to prove that ${2p - 1 \choose p} \equiv 1 \pmod{p^2}$ ? I don't want to use Wolstenholme's theorem; but one might use $p|{p \choose k} , 1 \le k \le p - 1$ , and $(p - 1)! \sum_{k = 1}^{p - 1} ...
0
votes
1answer
37 views

Induction divisibility proof

Prove that $4^n \sum_{k=0}^{n} \binom nk +14n-1 $ is divisible by $7$ for every $n \geq 1$. Basic Step: For $n=1$, $21$ is divisible by $7$.($21 \mod 7 = 0$) Induction Hypothesis: Suppose that ...
2
votes
1answer
53 views

implication of a number dividing a product of relatively prime numbers

I read this recently on the web and can't manage to understand it. Not homework -- I haven't done math homework for years. If $d|ab$ and $(a,b)=1$, prove that $d=d_1 d_2$, that $d_1|a$, that $d_2|b$, ...
4
votes
3answers
107 views

Can we prove the existence of a gcd in $\mathbb Z$ without using division with remainder?

For $a,b\in\mathbb Z$ not both $0$, we say $d$ is a gcd of $a$ and $b$ if $d$ is a common divisor of $a$ and $b$ and if every common divisor of $a$ and $b$ divides $d$. With this definition, can we ...
1
vote
1answer
19 views

Use the euclidean algorithm to prove that if gcd(a,b) = 1 and a|c and b|c then ab|c

I am a bit confused here. I assume that: $gcd(a, b) = 1 \wedge c = ax_{1} \wedge c = bx_{2}$. I tried to find a formula starting from $a = bx_{3} + r$. But I didn't succeed, any tips?
0
votes
1answer
32 views

Which subrings $S$ of $\mathbb Z_n$contains a multiplicative identity , that is $\exists e\in S$ such that for every $x \in S , x.e=e.x=x$ ?

I want to find all non-trivial subrings of $\mathbb Z_n$. So let $S$ be a subring (not necessarily containing $[1]$ ). Then $(S,+)$ is a asubgroup of $(\mathbb Z_n,+)$, so $S$ is generated by an ...
1
vote
3answers
68 views

Prove $(n!-1,(n-1)!-1)=1$

Question: Let $n\geq2,n\in\mathbb{N}$. Prove $(n!-1,(n-1)!-1)=1$ I have noticed that $n!=n\cdot (n-1)!$ So letting $\alpha=(n-1)!$, we have to prove $(n\alpha-1,\alpha-1)=1$ I feel that this is ...
1
vote
1answer
31 views

Long division to primitive roots?

In this long divsion: ...
1
vote
1answer
39 views

Euclid’s Algorithm as a State Machine. Why is the set of states is N^2?

In the textbook that I am reading it is said: Euclid’s algorithm can easily be formalized as a state machine. The set of states is $N^2$ and there is one transition rule: $(x,y) --> (y, ...
11
votes
1answer
69 views

Does it follow that $(n!)^n$ divide $(n^2)!$

It is well known that $(n!)^2$ divides $(2n)!$. Does it follow that $(n!)^3$ divides $(3n)!$ and so on up to $(n!)^n$ dividing $(n^2)!$? If yes or no, could you provide the details behind the ...
1
vote
1answer
41 views

$k$ divides $\binom{kn}{n}$

For positive integers $k,n$ , is it true that $k$ divides $\binom{kn}{n}$? I can write $$\binom{kn}{n}=\frac{(kn)(kn-1)\cdots(kn-n+1)}{n(n-1)\cdots 1}$$ but must the $k$ at the top remain after ...
1
vote
3answers
87 views

Prove or disprove : if $x|y^2 $then $x|y$

How can I prove such statement? I think that if $x|y^2$ then $x|(y*y)$ so $x|y$ or $x|y$ which means that in any case $x|y$. Am I correct? I ask this question as such template because I think that ...
0
votes
0answers
20 views

Given an array, how many no. of subsequnces of array such that gcd of numbers in that subsequence will be between a and b

A sub-sequence can be obtained from the original sequence by deleting 0 or more integers from the original sequence. L <= GCD(all numbers in subsequence) <= R number of such sequences. For ...
11
votes
4answers
2k views

How many three digit numbers are not divisible by 3, 5 or 11?

How many three digit numbers are not divisible by 3, 5, or 11? How can I solve this? Should I look to the divisibility rule or should I use, for instance, $$ \frac{999-102}{3}+1 $$
0
votes
3answers
110 views

If $p$ divides $a^n$, how to prove/disprove that $p^n$ divides $a^n$? [duplicate]

The only thing I know for this problem is that an integer is a product of primes.
3
votes
4answers
68 views

Prove that $(n^2-1)\mid(n^3+1)$ iff $n=2$

Seperating $n^2-1$ into $(n+1)(n-1)$. I have noticed that $n^3+1=(n+1)(n^2-n+1)$, so we have $\forall n\geq 2$, $(n+1)\mid(n^3+1)$. We now need to show that $(n-1)\mid(n^2-n+1)$ iff $n=2$ This ...
1
vote
2answers
30 views

Is it true that GCD$(\alpha,b)=1$?

Let $d=$GCD$(a,b)$, and $\alpha,\beta\in\mathbb Z$ such that $\alpha\cdot a+\beta \cdot b=d$. Is it true that GCD$(\alpha,b)=1$?
1
vote
1answer
33 views

Prove that an r-cycle to a power k where gcd(r,k)=d>1 is a product of d disjoint cycles of length r/d.

Let $\sigma$ be an $r$-cycle and let $k \in\Bbb N$. Let $d=\gcd(r,k)$. Write $r'=r/d$ and $k'=k/d$. Prove that $\sigma^k$ is a product of $d$ disjoint cycles each of length $r'$. I think ...
1
vote
2answers
125 views

Divisibility Proof with Induction - Stuck on Induction Step

I'm working on a problem that's given me the run around for about a weekend. The statement: For all $m$ greater than or equal to $2$ and for all $n$ greater than or equal to $0$, $m - 1$ divides $m^n ...