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

learn more… | top users | synonyms (1)

0
votes
0answers
12 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$, ...
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 ...
0
votes
1answer
13 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. ...
0
votes
2answers
59 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!
2
votes
1answer
51 views

Using gauss's lemma to find $(\frac{n}{p})$ (Legendre Symbol)

Sorry if this ends up being long. So basically, i am trying to understand the proofs of Gauss's lemma for things such as $(\frac{2}{p})$ $(\frac{3}{p})$ etc For $(\frac{2}{p})$ i am given this ...
3
votes
4answers
134 views

How to notate all integers $\gt 1$ except products of $2, 3 , 5$?

What is a notation for all whole numbers greater than $6$ which are not a product of $2, 3 , 5$? $7$ would the first, then $11, 13, \ldots$ also $7\times 7$ or $11\times 11$ would be included. As a ...
1
vote
1answer
15 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 ...
3
votes
3answers
374 views

Landau's “Foundations of Analysis” - Addition of natural numbers

At the beginning of his Foundations of Analysis book (translated from German), Landau writes in his Preface for the Teacher : Peano defines $x+y$ for fixed $x$ and all $y$ as follows : $$x+1 = ...
9
votes
4answers
149 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$ ...
11
votes
4answers
2k views

Proving that a number is an integer.

Prove that the following number is an integer: $$\left( ...
-5
votes
1answer
32 views
7
votes
1answer
152 views

Conjectured compositeness tests for $N=b^n \pm b \pm 1$

How to prove that these conjectures are true? Definition: Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$, where $m$ and $x$ are nonnegative ...
0
votes
3answers
51 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 ...
2
votes
2answers
49 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$$ ...
2
votes
3answers
45 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, ...
5
votes
1answer
57 views

Integers which are the sum of non-zero squares

Lagrange's four-square theorem states that every natural number can be written as the sum of four squares, allowing for zeros in the sum (e.g. $6=2^2+1^2+1^2+0^2$). Is there a similar result in which ...
3
votes
1answer
92 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 ...
5
votes
4answers
116 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 ...
3
votes
1answer
39 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$ ...
1
vote
2answers
65 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 ...
0
votes
0answers
35 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)?
3
votes
1answer
215 views

Conjectured primality test for specific class of $N=k\cdot 6^n-1$

How to prove that this conjecture is true ? Definition : $\text{Let}~ P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)~ , \text{where}~ m ~\text{and}~ x ...
6
votes
6answers
177 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
3answers
845 views

Proving that $C$ is a subset of $f^{-1}[f(C)]$

More homework help. Given the function $f:A \to B$. Let $C$ be a subset of $A$ and let $D$ be a subset of $B$. Prove that: $C$ is a subset of $f^{-1}[f(C)]$ So I have to show that every element ...
-1
votes
2answers
70 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
59 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 ...
3
votes
5answers
378 views

Prove that $3a^2-1$ is never a perfect square when $a$ is an integer

Prove that $3a^2-1$ is never a perfect square when $a$ is an integer. I'm not sure how to go about this proof or what form of an integer to use. I know an integer can be represented using ...
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 ...
4
votes
1answer
20 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 ...
2
votes
1answer
30 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 ...
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 ...
2
votes
4answers
57 views

If $S$ is the set of all numbers of the form $3k + 1$, prove that any number $a$ in the set is prime or product of primes.

$S = \{1, 4, 7, 10, \ldots \}$ $10$ and $25$ are prime with regard to the elements of $S$ but $16 = 4 \times 4$ and $28 = 7 \times 4$ are not. I have been stuck on this problem as I am not sure of ...
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 ...
-2
votes
1answer
50 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
68 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.
0
votes
0answers
27 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
40
votes
3answers
2k views

If the decimal expansion of $a/b$ contains “$7143$” then $b>1250$

I recently stumbled upon this really interesting problem: Suppose we have a fraction $\frac{a}{b}$ where $a,b \in \mathbb{N}$ and we know that the decimal fraction of $\frac{a}{b}$ has the ...
5
votes
1answer
37 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 ...
7
votes
3answers
216 views

Conjectured compositeness tests for $N=k \cdot 2^n \pm c$

How to prove that these conjectures are true ? Definition : $\text{Let}~ P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)~ , \text{where}~ m ...
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 ...
7
votes
3answers
229 views

Conjectured Primality Test for $N=8\cdot 3^n-1$

Definition Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ , where $m$ and $x$ are nonnegative integers . Conjecture Let $N=8\cdot 3^n-1$ ...
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 ...
1
vote
1answer
69 views

Proof concerning specific class of Proth numbers

Is this proof acceptable ? Theorem Let $N = k\cdot 2^n+1$ with $n>1$ , $k<2^n$ , $k$ odd and $3 \nmid k $ , thus $N$ is prime iff $3^{\frac{N-1}{2}} \equiv -1 \pmod N$ Proof Necessity ...
-5
votes
2answers
43 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$?
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
4answers
292 views

Prove that $\log_9 15$ is irrational

Im having trouble with the following proof... Ill post what I have completed so far.. Prove that $\log_915$ is irrational. Ill attempt by contradiction assuming $\log_915$ is rational. So, ...
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 ...
12
votes
3answers
925 views

Intermediate digits of 34!

Problem: Given that $34!=295232799cd96041408476186096435ab000000$. Find $a, b, c, d$. $a, b, c, d$ are single digits. I am able to find $a$ and $b$ but cant find $c, d$. I did the prime factorisation ...
4
votes
3answers
105 views

Prove $\log_7 n$ is either an integer or irrational

I have been trying to prove a certain claim and have hit a wall. Here is the claim... Claim: If $n$ is a positive integer then $\log_{7}n$ is an integer or it is irrational Proof ...