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

learn more… | top users | synonyms (1)

0
votes
0answers
15 views

The equation $a^2x^3+y^3=az^3$

An example of equation with a particular numerical value of $a\in\mathbb N$, I have extended to a family of equations that I present here. Prove the equation $$a^2x^3+y^3=az^3; (x,y,z)\in\mathbb ...
2
votes
2answers
19 views

Cicada emergence intersections (13 and 17 year)

There are 2 periodic cicada species in my area. One emerges every 13 years. The other every 17 years. Both are prime numbers, which is interesting but not necessarily related to my question. I ...
0
votes
0answers
38 views

Division of polynomials in $\mathbb{Z}[x]$

Theorem: ?For $f\in \mathbb{Z}[x]$ and $p$ prime if $\exists a\in \mathbb{Z} : f(a)\equiv 0\pmod p $ then $f(x)\equiv f_1(x)(x-a)\pmod p$ for some $f_1\in \mathbb{Z}[x]$ The proof is simple argument ...
1
vote
1answer
26 views

Are we allowed to choose real variables in elementary number theory problems

For example, dis/prove each of the following statements If $p$ is prime and $p \mid (a^2 + b^2)$ and $p \mid (c^2 + d^2)$, then $p \mid (a^2 - c^2)$ If $p$ is prime and $p \mid a$ and $p ...
2
votes
2answers
20 views

Quadratic form has non-trivial zero?

For each of the following quadratic forms, determine whether the form has a non-trivial zero (we do not need to exhibit it): $f(x, y, z) = 2x^2 + 3y^2 - 6z^2$; $g(x, y, z) = 2x^2 + 3y^2 - ...
6
votes
2answers
53 views

$a,b,c\in \Bbb Z$ and $a\cdot b\cdot c$ is a root of $ax^2+bx+c$.

I was curious if there are quadratic equations where $a,b,c\in \Bbb Z$ and $a\cdot b\cdot c$ is a root of $ax^2+bx+c$. So trivially if $c=0$, $a$ and $b$ can be arbitrary, and if either $a$ or $b$ is ...
9
votes
1answer
55 views

Prove that a given expression is always an integer [duplicate]

Given integers $x_1, x_2, \dotsc, x_n$, prove that the expression $$ \prod \limits_{1\leq i<j\leq n}\frac{x_i - x_j}{i-j} $$ is always an integer. I think induction should work, but I ...
2
votes
1answer
40 views

Integer solutions of $xy+xz+yz-2xyz=0$

I have to find the positive integer solutions of the equation $$xy+xz+yz-2xyz=0.$$ Note: If there are solutions, they should be finite in number because $xyz$ is of third degree.
2
votes
1answer
24 views

Prove $m-n$ and $2m+2n+1$ are coprime

I have a small problem: Let $m$ and $n$ be integers such that $2m^2+m = 3n^2+n$. Prove that $m-n$ and $2m+2n + 1$ are perfect square. My work: We have $$(m-n)(2m+2n+1) = 2(m^2-n^2) + m-n = ...
5
votes
2answers
30 views

How can one go around dividing by zero when simplifying?

I have the expression $$\frac{1}{2}i\log\left(1-e^{\frac{2i\pi{x}}{b}}\right)-\frac{1}{2}i\log\left(1-e^{-\frac{2i\pi{x}}{b}}\right)$$ and I want to simplify it without getting any division-by-zero ...
2
votes
2answers
78 views

Prove $p$ is prime

Let $p$ be an integer with this property: whenever $b, c \in \mathbb Z$ such that $p\mid bc$, then $p\mid b$ or $p \mid c.$ Prove $p$ is prime. Here is my attempt at a proof: Suppose $d \mid p$. Then ...
1
vote
2answers
50 views

Maximum possible gcd of integer elements, whose sum is 540.

What would be a maximum possible GCD of $a_1, a_2, ... a_{49} \in \mathbb{N}$ . Given that $$ a_1 + a_2 + ... + a_{49} =540 $$ The answer from the book is 10. I was trying to solve it using linear ...
0
votes
1answer
19 views

Figuring out variable pairs in an inequality

Let $x$ and $y$ be positive integers such that $45 < 8x + 5y < 60$ How many $(x,y)$ pairs can be found? (Ans: 16) Of course, there is a way to write it one by one. On the other hand ...
0
votes
0answers
34 views

How to compute the correct residue without change of modulus?

Suppose $F=1857$, $G=2017$, and we want to compute $ FG \equiv 1606$ mod $(2^{11} -1)$. Also let $t =2^4$, then $F = 1+4t+7t^2$ and $G = 1+14t+7t^2$, where the most significant digits are bounded ...
0
votes
1answer
33 views

For $ \frac{n(n-1)}{2}<i \leq \frac{ n(n+1)}{2} $, why is $\text{round}(\sqrt{2i})=n$

I was doing Problem 67 of Project Euler, which involves number triangle which has similar structure to Pascal's triangle (the nth row contains n numbers). While thinking of a way to represent the ...
1
vote
2answers
44 views

When does $x^n - a$ have rational solutions?

Let $f(x) = x^n - a$ be a polynomial with integer coefficients, when does $ f (x) $ have rational solutions? Is there a necessary and sufficient condition? I understand this is equivalent to ...
-1
votes
2answers
193 views

Is this basic fact about prime pairs obvious?

$A_p = \{\text{prime } q: p + 2k = q \text{ for some } k \in \Bbb{Z}\}$ is the same set for any prime $p \geq 3$. Is this obvious?
0
votes
0answers
20 views

Limit of the ratio of the square root of a Mersenne number to the product of its prime factors

Mersenne numbers with prime exponents are numbers of the form $M_p = 2^p-1$, where $p$ is prime. Suppose that $p$ is such that $M_p$ has exactly two prime factors, $\rho, P$. Given $\epsilon > 0$, ...
0
votes
2answers
62 views

$b$ divides $a \Leftrightarrow -b$ divides $a$

Prove that $b$ divides $a$ if and only if $-b$ divides $a$. I'm thinking something like $a = bp$ and $b = aq$, then go on from there? It seems simple enough but thanks for the help in advance!
1
vote
1answer
22 views

Proof of a complete residue system without using congruences

I am taking a elementary class on number theory this semester, and among the exercises from the third lecture there is this one: For $m > 1$ and $gcd(m, a) = 1$, show that the remainders from the ...
-6
votes
1answer
36 views

What is the sum of the factors of nine [on hold]

what is the sum of the factors of nine
0
votes
1answer
15 views

finite-state machine for a system

Every cycle we get a bit $x_t$. We output $1$ iff $$(x_1\ldots x_t) \bmod 5 = 2 \lor (x_1\ldots x_t) \bmod 5 = 4$$ I need to design an FSM (preferably Mealy machine but that doesn't really matter. ...
2
votes
1answer
110 views

Elementary Twin Prime Attempt. [on hold]

There's a theorem somewhere that for sufficiently large $k$ there exists an infinite number of prime pairs with difference $2k$. Let $\ell$-prime pair mean a pair of primes separated by a distance of ...
2
votes
2answers
50 views

A property of every set of ten consecutive integers.

In the following example of ten consecutive integers we can see that $119$ and $121$ are each coprime with the others: $$114=2*3*19$$ $$115=5*23$$ $$116=2^2*29$$ $$117=3^2*13$$ $$118=2*59$$ ...
3
votes
1answer
42 views

Can two distinct sets of $N$ non-negative numbers have the same sum and sum of squares?

Suppose I have a set of $N$ non-negative numbers that sum to $A$. The sum of squares of these $N$ non-negative numbers sum to $B$. Here's the question: can there be a different set of $N$ ...
2
votes
4answers
55 views

Find last two digit

I have the following task: $1997^{1998} \pmod {100} = ?$ How to find it? Could you please, explain to me step by step with? Can you suggest any solution, without using Euler function? But rather, ...
0
votes
0answers
36 views

Does this set contain these numbers?

How would I go about proving whether or not every number $n=k^8$ is included in the set of all numbers $m=k^4$ ($n$ and $k$ are integers in both cases)?
5
votes
4answers
117 views

How many ways to write $2010$?

Let $ N$ be the number of ways to write $ 2010$ in the form $ 2010 = a_3 \cdot 10^3 + a_2 \cdot 10^2 + a_1 \cdot 10 + a_0$, where the $ a_i$'s are integers, and $ 0 \le a_i \le 99$. An example of ...
-1
votes
2answers
72 views

Proof that expression is integer, $\frac{(2n)!}{n!(n+1)!}$

can you help me with this excercises.. Proof that expression is integer, $$\frac{(2n)!}{n!(n+1)!}$$ I've tried for induction!! $p(1):\frac{(2)!}{2}=1 $ for $p(k)=\frac{(2k)!}{k!(k+1)!}$ for ...
2
votes
3answers
60 views

Proof that expression is integer, $\frac{(3n)!}{6^nn!}$

Can you help me with this exercises? Proof that expression is integer, $$\frac{(3n)!}{6^nn!}$$ I've tried for induction!! $p(1):\frac{(3)!}{6}=1 $ for $p(k)=\frac{(3k)!}{6^kk!}$ for ...
0
votes
3answers
54 views

The sum of all numbers between 1 and 1000 (inclusive) that are divisible by 3 or 5, but not both

I found a problem that asked to calculate the sums of all numbers between $1$ and $1000$ (inclusive) that are divisible by $3$ or $5$, but not both. I immediately thought of Gauss which made me smile ...
1
vote
1answer
12 views

Minimum of restricted linear combinations.

Let $\{N_0, ... , N_m\}$ be a set of natural numbers, then the minimum $(\geq 1)$ of all their linear combinations is their GCD. Is there a way to calculate that minimum if some $N$s can only be ...
6
votes
3answers
49 views

What phenomenon is this? $(2\Bbb{Z} + 1)\cup 3\Bbb{Z} = 2\Bbb{Z} \cup 3\Bbb{Z} + 3$

$(2\Bbb{Z} + 1)\cup 3\Bbb{Z} = 2\Bbb{Z} \cup 3\Bbb{Z} + 3$ Proof: $$ \begin{align*} 2\Bbb{Z} &= \bullet \circ \bullet \circ \bullet \circ \bullet \circ \dots \\ 3\Bbb{Z} &= \bullet \circ ...
2
votes
1answer
31 views

significance of Burton number theory exercise

Here is the question in Burton - I can solve it but am not sure what the importance of this exercise is and what Burton is trying to help me see with it: Find a prime divisor of the integer ...
4
votes
1answer
21 views

Properties of the Digit Product + Digit Sum of a number

The other day I started messing around with some properties and noticed a pattern emerging when the digit product and digit sum of a number were added together. For example, 15. (1+5)+(1*5) = 11. If ...
0
votes
1answer
10 views

For two periodic sets $A,B$, $A \cup (B + \{x\}) = \{y\} + A \cup B$ for some $y \in \Bbb{N}$.

Let $A,B$ be periodic subsets of $\Bbb{N}$, in other words each has an associated $T \in \Bbb{N}$ such that if $x \in A$, then $x + T \in A$, always, for instance. Let $x + A$ mean a translate of ...
0
votes
0answers
28 views

Moebius Identity

Is there alternative proof of Moebius identity i.e. sum of moebius function over divisor of n is zero than as suggested n page: ...
0
votes
0answers
13 views

Dirichlet product is associative

Is there alternative proof of fact: Dirichlet product on arithmetic function is associative than given in Dirichlet's product with number theoretic functions
1
vote
1answer
19 views

Every collection of periodic sets $A_n \subset \Bbb{N}$ (minus a common point), that avoids…

Let $\{A_n\}$ be a set of subsets of $\Bbb{N}$ each of which are periodic except for a common point. That is to say, there exists one and only one $x_0$, such that for each $n$, if $x \in A_n, x \neq ...
9
votes
4answers
153 views

Diophantine equation $(x+y)(x+y+1) - kxy = 0$

The following came up in my solution to this question, but buried in the comments, so maybe it's worth a question of its own. Consider the Diophantine equation $$ (x+y)(x+y+1) - kxy = 0$$ For $k=5$ ...
5
votes
1answer
43 views

Let $a$ and $m$ be positive integers such that gcd$(a,m)=1$. Show that: $a^m+1$ is not a prime.

Let $a$ and $m$ be positive integers such that gcd$(a,m)=1$. Show that: $a^m+1$ is not a prime. Though I didn't check the statement with so many integers, but it looks like the equation never ...
2
votes
1answer
37 views

How to prove the sum of squares larger than 1/n without induction? [duplicate]

known that: $1\geq R_1 \geq R_2 \geq \dots \geq R_n \geq 0$ and $\sum_{i=1}^n R_i=1$ To prove: $\sum_{i=1}^n R_i^2 \geq \frac{1}{n}$ Using induction, the problem can be easily proved. I'd like to ...
1
vote
2answers
31 views

Number 9 and age of mother when child is born.

If a mother's age is divisible by 9 when a child is born then once you go to the next decade,n every 11 years the child's age and mother's age are always the same two numbers in reverse order. For ...
0
votes
0answers
24 views

Prove that for every $k$ there exist fibonnaci number that ends with $k$ zeros.

Let $F_1 = F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n > 2$. Prove that for every $k$ there exist $F_m$ that ends with $k$ zeros. I tried using pigeonhole principle, but with no effect.
1
vote
2answers
66 views

“Proof” that $(2n)!$ is divisible by $2^n 5^{n-3}$ for $n\ge3$

Please explain, as clearly as possible, what is wrong with the following "proof" by induction that $\hspace{1.4 in}$$(2n)!$ is divisible by $2^n 5^{n-3}$ for $n\ge3$. (There clearly must be an ...
-5
votes
2answers
45 views

4th Grade Common Core question [on hold]

In the number $2,119$ if you move from the $1$ in the hundreds place to the $1$ in the tens place, what happens to the value of the $1$?
2
votes
0answers
20 views

Lehmer's totient problem generalization (adding a constant )

Lehmer's conjecture is an well-known open problem which states that the divisibility : $$\phi(n) \mid n-1$$ holds only for primes . This motivated me to ask the following : For which ...
6
votes
6answers
181 views

How is $\mathbb N$ actually defined?

I know perfectly well the Peano axioms, but if they were sufficient for defining $\mathbb N$, there would be no controversy whether $0$ is a member of $\mathbb N$ or not because $\mathbb N$ is ...
-2
votes
1answer
51 views

Solving problem of abstract algebra [on hold]

The question is that if $n$ is not a multiple of 23 then the remainder when $n^{11}$ is divided by 23 is 1 or -1(mod 23). Is it true or false? Please answer me.
3
votes
0answers
69 views

Solving an equation $x^{22}\equiv2 \bmod 23$ [on hold]

I have an abstract algebra problem which I am unable to solve. The problem is, if $x^{22}\equiv2 \bmod 23$, then $x$ has how many solutions? Please explain me.