Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms (1)

-2
votes
1answer
83 views

Proof by induction that certain number is an integer

Prove that the number $\frac{2n^5}{5} + \frac{n^4}{2} - \frac{2n^3}{3} - \frac{7n}{30}$ is an integer $\forall n \in \mathbb{N}.$
5
votes
2answers
77 views

Find the values of $k$ for which $\sqrt{1+\frac{k}{n}}$ is irrational for all $n\in\mathbb N$

I would like to find the positive integers $k$ for which $\sqrt{1+\frac{k}{n}}$ is irrational for all $n\in\mathbb{N}$. I was led to this question when I was making up an example for my class, and I ...
0
votes
2answers
115 views

Does $x^2 + x + 1 \equiv 0 \mod p$ have a solution?

Problem: I am trying to prove that $$ x^2 + x + 1 \equiv 0 \mod p $$ has a solution where $p$ is a prime such that $p \equiv 1 \mod 3$, without using quadratic reciprocity. I am also suspecting that ...
1
vote
2answers
36 views

how to know when a particular proof is appropriate for the given problem?

The main trouble I am currently having in math is knowing when the use cases are appropriate in a proof. I see many videos where they seem to choose a strategy like proof by contrapositive or proof by ...
3
votes
1answer
182 views

Find the number of possible 4x4 matrices such that :

Find the number of possible 4x4 matrices such that : 1) each row has two 0's and two 1's 2) each column has two 0's and two 1's example : $$\large \begin{pmatrix} 1&1&0&0\\1&1&0&...
1
vote
1answer
138 views

Suppose $x \in \mathbb{R}$. If $x^3-x>0$, then $x>-1$. Contrapositive proof

Suppose $x \in \mathbb{R}$. If $x^3-x>0$, then $x>-1$. Proof (Contrapositive). Suppose $x \leq -1$. It follows that $x^3 \leq x \leq -1$. Picking $x=-1$, the quantity $x^3-x=0$, otherwise it is ...
0
votes
1answer
79 views

Prove: If $G$ has an element of order $k$ and an element of order $m$, the order of $G$ is a multiple of lcm(k,m).

Prove: If $G$ has an element of order $k$ and an element of order $m$, the order of $G$ is a multiple of lcm(k,m). This is the same as asking to show if $k\mid n$ and $m\mid n$ then $q \mid n$. Where ...
2
votes
0answers
25 views

Proof of divisibility using factorials [duplicate]

Prove that for all $n, a \in \mathbb Z$, $n!|(a+1)(a+2)...(a+n)$. I was thinking I could do this by induction but I'm a little stuck. Here's what I have: Basis: For $n=1$, $a \in \mathbb Z$, $n!...
1
vote
1answer
17 views

Proof using GCDs

Given $a, b, c \in \mathbb Z$, no more than one of which is zero. Let $g_a$ denote $\gcd(a,c)$. Let $g_b$ denote $\gcd(b,c)$. Also given that $a, b$ relatively prime. Prove that $\gcd(g_a,g_b) = 1$...
0
votes
1answer
108 views

Proof related to RSA decryption

Can someone help me with this proof: Show that RSA decryption works for all messages a as long as the modulus m is a product of distinct primes. Thank you.
1
vote
1answer
47 views

simple question about number theory

Is there a name to the theorem that says for integers $a,b,c$ where $a$ is prime, if $a\mid bc$ and $(a,b)=1$ then $a\mid c$
1
vote
1answer
95 views

Show the congruence $x^2 \equiv a \mod p^{k+1}$ has exactly two solutions…

Show that if $p$ is an odd prime, $p \nmid a$, and the congruence $x^2 \equiv a \mod p^k$ has exactly the solutions $x \equiv \pm t \mod p^k$, then the congruence $x^2 \equiv a \...
0
votes
1answer
913 views

find the least positive residue of $1!+2!+3!+…+100!$ modulo each of the following integers

I am trying to find the least positive residue of $1!+2!+3!+...+100!$ modulo each of the following integers: a) $2$ b) $7$ c) $12$ d) $25$ and I am stuck on how to do this. I know that you have ...
2
votes
2answers
59 views

In $\mathbb{Z}_q$ where $q$ is prime, show that $[a^q]=[a]$ for all $[a]\in \mathbb{Z}_q$

Question: In $\mathbb{Z}_q$ where $q$ is prime, show that $a^q=a$ for all $a\in \mathbb{Z}_q$. My attempt: To show $[a^q]=[a]$ for all $[a]\in \mathbb{Z}_q$, it suffices to show that for any $a\in\...
0
votes
1answer
155 views

Construction of uncountably many non-isomorphic linear (total) orderings of natural numbers

I would like to find a way to construct uncountably many non-isomorphic linear (total) orderings of natural numbers (as stated in the title). I've already constructed two non-isomorphic total ...
1
vote
2answers
72 views

$\prod\limits_{i=1}^n \frac{3a_i+2}{2a_i+1}, a_i\geq 1$

$$\prod\limits_{i=1}^n \frac{3a_i+2}{2a_i+1}, a_i\geq 1$$ Claim: This product is never an integer ($a_i$ integer).
4
votes
3answers
269 views

What is the most elementary way of proving a sequence is free of non-trivial squares?

Given the sequence A001921 $$ 0, 7, 104, 1455, 20272, 282359, 3932760, 54776287, 762935264, 10626317415, 148005508552, 2061450802319, 28712305723920, 399910829332567, \dots $$ which obeys the ...
2
votes
2answers
55 views

How to show that $n^{n!} \gt (n!)^{n}$ for $n\gt 2 \in \mathbb{N}$

Show that $n^{n!} \gt (n!)^{n}$ for $n\gt 2 \in \mathbb{N}$ I have tried induction taking the base case $n=3$ It is not going smooth however I am looking for some simpler proof, induction or ...
1
vote
3answers
37 views

Factorization probability

I'm interested in factoring large numbers. I would like to know that if I take a normal laptop and implement for example general or special number sieve and let it run all the time, what would be the ...
2
votes
1answer
65 views

Irrationality of the concatenation of decimal expansions of primes

I've heard the proof that this number is irrational is accessible to even a novice to number theory: $\alpha = 0.2 \ 3 \ 5 \ 7 \ 11 \ 13 \ 17 \ldots$ The proof may utilize that a number is ...
0
votes
2answers
217 views

Compute largest integer power of $6$ that divides $73!$

I am looking to compute the largest integer power of $6$ that divides $73!$ If it was something smaller, like $6!$ or even $7!$, I could just use trial division on powers of $6$. However, $73!$ has $...
1
vote
3answers
171 views

Proof of the Principle of mathematical Induction [duplicate]

We always use the Principe of Mathematical induction and we have two versions of it. I myself have been using it for many years. But it just came to my mind that I have never seen a proof of the ...
0
votes
1answer
167 views

A number relatively prime to n in the integers mod n produces all the elements

Say that two integers $a,n$ are coprime. Then $r[a]_n$, where $[a]_n$ denotes the equivalence class of $a$ in the integers mod $n$, generates all the equivalence classes for the values $0<r<n+1$....
-1
votes
1answer
94 views

any computational analytic number theory book?

All: Can anyone recommend an introduction computational analytic number theory book ? I am mainly interested in using computer software to verify and confirm analytic number theorem, things related: ...
2
votes
1answer
21 views

How do I prove that $R=\{(x,y) \in S \times S : x\text{ divides }y\}$ is antisymmetric?

$S=\{1, 2, 3,\ldots, 1000\}$ $R=\{(x,y) \in S \times S: x \mid y\}$ My attempt: Assume $xRy$ and $yRx$. Then $x=ym$ and $y=xn$ for $m$, $n$ in Natural numbers. -So $x=xxn..$ that gets me nowhere. ...
2
votes
3answers
53 views

Solve $9x$ $\equiv 4 \mod1453$

In Underwood Dudley's Number theory book second edition chapter 5 problem 7 I encountered this problem: Solve $9x\equiv 4 \mod1453$ I know that since $gcd(9,1453)=1$, there exists a unique solution. ...
4
votes
1answer
48 views

GCD of adjacent pairs take on all possible values

Given a fixed positive integer $n$. Consider the numbers $1,2,\ldots,2n$. The GCD of any pair is one of $1,2,\ldots,n$. Suppose that all $2n$ numbers are placed around a circle. Is it possible that ...
0
votes
1answer
60 views

General Behavior of Euler Totient Function

If we have two integer M and N such that $$GCD(M,N) = k$$ Then what is $$\phi(MN)$$ There is a famous identity which states: $$GCD(M,N)= 1 \rightarrow \phi (MN) = \phi(M)\phi(N)$$ And now I am ...
1
vote
3answers
83 views

Where did the sum-of-divisors function come from?

Doing a research project on a few number-theoretic functions, and I was curious, where does the sum-of-divisors function come from? Surely someone thought it up and made it a possibility. I'm talking ...
1
vote
1answer
35 views

Easy (?) estimation about prime powers

Let $N_k$ be some integers with $\sum_{k\mid n}kN_k=p^n$. How can I prove $$\frac{p^n}{n}-\frac{2p^{n/2}}{n}\leq N_n?$$
0
votes
1answer
82 views

Summation of multiplicative function $f$ where $f(p) = 1$ for $p$ prime

I have a multiplicative function $f$ with a special "base" case: For every prime $p$, $f(p) = 1$. E.g. splitting up $f(3^5 \times7^2 \times 13 \times 17)$ yields $f(3^5) f(7^2)$ which is left to be ...
1
vote
1answer
49 views

Proving that $a$ is an element of a set $A$

I am supposed to prove that if $a \in \mathbb{Z}$ and $a^2\mid a$, then $a \in \{-1,0,1\}$. If I let $B = \{-1,0,1\}$ and $\overline{B} = \mathbb{Z} \setminus B$, is it sufficient to show that $a \...
1
vote
2answers
181 views

Simple quadratic, crazy question part 2

In my previous question, I asked for advice on a general method to solve a specific problem. Many good ideas came from this, but the problem I gave was too simple and these approaches were sufficient ...
0
votes
2answers
50 views

Calculate the power series

I want to find the power series of $\frac{1}{3!}$ in the field $\mathbb{Q}_3$. In order to do this, do I have to solve the congruence $3!x \equiv 1 \pmod{3^n} \Rightarrow 6x \equiv 1 \pmod 3$? If so,...
0
votes
2answers
230 views

Can anyone explain how to do this number?

Let $x,y,z \in \mathbb R$ be real numbers such that $x, y, z, x+y, y+z, z+x$ are all non-zero, and such that $\frac{xy}{x+y} , \frac{yz}{y +z} , \frac{zx}{z +x}$ are integers (i.e. belong to $\mathbb ...
1
vote
1answer
55 views

Is my understanding right on the divisiblity rule?

For a given number and a divisor. If the prime factors of the divisor can divide a number,then can I say that the divisor will divide a number. For example - 786 divide by 21 If I break 21 in the ...
4
votes
1answer
174 views

Solve $3x^2-y^2=2$ for Integers

If $x$ and $y$ are integers, then solve (using elementary methods) $$3x^2-y^2=2$$ I tried the following If $y$ is even, then $4|y^2$ and hence $2|y^2+2$ (and $4$ doesn't divide it), but $3x^...
1
vote
2answers
54 views

How else could we solve the congruence?

How could I solve the congruence $6x \equiv 1 \pmod { 5^4}$? I wanted to use the formula $x_n=\frac{5^4+1}{6}$, but calculating this number, we see that it is not integer. How else could we solve ...
1
vote
1answer
54 views

If $a$ divides $b$, then $a$ divides $3b^3-b^2+5b$.

Prove: Suppose $a$ and $b$ are integers. If $a\mid b$, then $a\mid3b^3-b^2+5b$. I think I have an idea of how to prove this, but I'm not entirely sure. I can prove that each individual term in the ...
0
votes
2answers
65 views

What is the relation between $a$ and $b$?

Let $p$ be a fixed prime number, and $a,b$ two natural numbers satisfying $a>p,b>p$. Assume the following logical equivalence: $$a\equiv0\mod p\iff b\equiv0\mod p$$ So what is the relation ...
0
votes
1answer
45 views

Proving $2X^5 -10X+5$ is irreducible.

I'm trying to prove that $f(X)=2X^5 -10X+5$ is irreducible and the book that I'm following says that this is given by Eisenstein's Criterion. The problem is that I don't know how to use Eisenstein ...
0
votes
1answer
251 views

Equivalence classes of multiples of 3

I'm having a little trouble wrapping my head around the elements of the equivalence classes using the following definition: for m, n in N, define m ~ n if m^2 - n^2 is a multiple of 3. 1) List four ...
7
votes
3answers
879 views

What's wrong in this proof of $10$ is a solitary number?

Friendly numbers are two or more natural numbers with a common abundancy, the ratio between the sum of divisors of a number and the number itself. Two numbers with the same abundancy form a friendly ...
2
votes
1answer
40 views

How do I write out this proof?

The following works with any number greater than the number 9. How do I write the following examples out in a proof? Take the two digits in your age for example & add then add those two numbers. ...
0
votes
1answer
15 views

finding A using with restriction $1 \leq a \leq 20$ in GCD

For what $1 \leq a \leq 20$ you are finding $a$ is it true that $a^m+a^n=x^2$ for positive integers $a,m,n,x.$ I did $a^m+a^n=x^2.$ $=a^m(a^{n-m}+1)=x^2$ We know that since $(a,b)=1$ since the ...
-4
votes
2answers
137 views

How to show that $(a \sim b \iff n | a−b)$ is an equivalence relation? [closed]

Let $n \in \mathbb{Z}$, $n > 0$ be a fixed positive integer. Define the relation $\sim$ on the set $\mathbb{Z}$ of integers by setting $$ \forall a, b \in\mathbb{Z}\ (a \sim b \iff n | a−b). $$ ...
0
votes
1answer
46 views

What else could we do, instead of solving the congruences?

I want to find the p-adic expansion of $\frac{1}{p}$ and $\frac{1}{p^r}$ in the field $\mathbb{Q}_p$. So, do I have to solve the congruences $px \equiv 1 \pmod {p^n}, p^r x \equiv 1 \pmod { p^n }, \...
6
votes
1answer
105 views

Prove or disprove $\gcd(q,r) \mid b$ if $a = bq + r$

Prove or disprove $\gcd(q,r) \mid b$ if $a, b, q, r \in \Bbb{Z}^+ \ni a = bq +r$ I'm pretty sure it's true (I can't think of a counter example), but I don't see how to prove it. Some of my ...
3
votes
2answers
86 views

$1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\frac{1}{5}-\dots+\frac{1}{1331}=\frac{p}{q}$; is $p$ divisible by $1997$?

if $p,q\in \mathbb{N}$ and $$1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\frac{1}{5}-\dots+\frac{1}{1331}=\frac{p}{q}$$ why is $p$ divisible by $1997$?
1
vote
4answers
45 views

Prove $(n!)/n^n \leq 1/2^{k}$, where $k$ is the floor of $n/2$.

I suppose the natural way to prove this is by induction. When I follow the rather natural steps $$\frac{(n+1)!}{(n+1)^{n+1}} = \frac{n!}{(n+1)^{n}} \leq \frac{n!}{(n)^{n}}$$ in order to apply the ...