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

learn more… | top users | synonyms

1
vote
2answers
148 views

A couple of problems involving divisibility and congruence

I'm trying to solve a few problems and can't seem to figure them out. Since they are somewhat related, maybe solving one of them will give me the missing link to solve the others. $(1)\ \ $ Prove ...
-2
votes
2answers
89 views

Is $\prod_{i=1}^{r}a_i b_i = \prod_{i=1}^{r}a_i\prod_{i=1}^{r}b_i$?

Is $\prod_{i=1}^{r}a_i b_i = \prod_{i=1}^{r}a_i\prod_{i=1}^{r}b_i$? How you would prove it or is this trivial?
1
vote
2answers
705 views

Factoring n, where n=pq and p and q are consecutive primes

So in RSA, there is a modulus n which is the product of two primes. My question is regarding when p and q are consecutive primes, what would the time complexity be? So, n=pq and p and q are ...
1
vote
3answers
535 views

Prove that gcd exists and it is unique

How can I show using division algorithm on $\mathbb{N}$ that there is a gcd for every pair of number $a,b \in \mathbb{N}$ and this gcd is unique?
2
votes
2answers
208 views

How to prove this Pythagorean Triple?

How do I prove that $(2mn, m^2 - n^2, m^2 + n^2)$ is true for $m>n>0$? Since $m^2 + n^2$ is the hypotenuse, I applied the Pythagoren theorem: $(2mn)^2 + (m^2 - n^2)^2 = (m^2 +n^2)^2$ and ...
2
votes
1answer
70 views

Sequence finding

Find all such sequences $(x_1, x_2, x_3, ..., x_{63})$ consisting of different positive integers that for $n=1,2,3,...,62$ the number $x_n$ is a divisor of $x_{n+1}+1$ and $x_{63}$ is a divisor ...
10
votes
3answers
163 views

For which n are there primitive Pythagorean triples with legs of lengths a and a+n?

For which n can $a^{2}+(a+n)^{2}=c^{2}$ be solved, where $a,b,c,n$ are positive integers? I have found solutions for $n=1,7,17,23,31,41,47,79,89$ and for multiples of $7,17,23$... Are there ...
3
votes
2answers
196 views

Formula that takes on all integers

Given two integers $a,b$, how to prove that for every integer $z$, there exist integers $x,y$ such that $z=ay+bx+xy$ And how does one in general prove or disprove that a formula in one or more ...
7
votes
3answers
336 views

Which is the most restrictive closed-form expression that still generates all primes?

"The set $\{f(n)\}, n=1,2,\ldots$ includes all primes except a finite number of exceptions." This statement is true for $$f(n)=\sqrt{1+24n},$$ for which the exceptions are 2 and 3. It also generates ...
0
votes
2answers
172 views

Why is this not working? (Chinese remainder theorem weird result)

Trying to find $x \equiv_{17} -4$, $x \equiv_{23} 3$. OK, so $x = -4 + 17k$ for some $k$. $-4 + 17k \equiv_{23} 3$. Since $19$ is the inverse of $17 \pmod {23}$, $k \equiv_{23} (3+4)19 \equiv ...
0
votes
2answers
317 views

Summing up all $N$ digits automorphic numbers

In mathematics an automorphic number (sometimes referred to as a circular number) is a number whose square "ends" in the same digits as number itself. Thus $5$ is automorphic since $25$ ends in ...
2
votes
1answer
95 views

For a prime $p$, determine the number of positive integers whose greatest proper divisor is $p$

I'm having a bit of difficulty writing a graceful proof for the following problem: For a prime $p$, determine the number of positive integers whose greatest proper divisor is $p$. Let $A$ be the ...
2
votes
1answer
103 views

With what probability is this polynomial equal to zero (mod a prime $p$)?

If we suppose that we have a polynomial $q(x)$ of the following form: $q(x) = \sum_{i=0}^N{c_i x^i} \text{ where } c_i=0 \text{ or } c_i=1$ In other words, if we are given a polynomial with binary ...
22
votes
1answer
614 views

Always oddly-many ones in the binary expression for $10^{10^{n}}$?

Update: Pending independent verification, the answer to the title question is "no", according to a computation of $q(10) = 11609679812$ (which is even). Let $q(n)$ be the number of ones in the ...
-2
votes
1answer
107 views

Primes classifications [closed]

1) If $p_1$$p_2$,...,$p_k$ be different primes and m = product of primes $p_1$,$p_2$,...,$p_k$ . How to prove that, when N = $N_1$ + $N_2$+...+$N_k$, where the prime factors of $N_i$ (here i is ...
5
votes
5answers
729 views

Determine the Set of a Sum of Numbers

I want to determine the set of natural numbers that can be expressed as the sum of some non-negative number of 3s and 5s. $$S=\{3k+5j∣k,j∈\mathbb{N}∪\{0\}\}$$ I want to check whether that would be: ...
0
votes
2answers
167 views

Divisibility tests for all numbers

If $(m, 10) = 1$, choose $b$ so that $10 b \equiv 1 \pmod m$. Then $n \equiv 0 \pmod m$ if and only if $n' + ba_0 \equiv 0 \pmod m$, where $a_0$ is the unit's digit of $n$, and ...
4
votes
1answer
218 views

$16$ natural numbers from $0$ to $9$, and square numbers: how to use the pigeonhole principle?

There are $16$ natural numbers placed next to each other. Each is a number from $0$ to $9$. These are in any order, and you can have as many repeats as you want (e.g. all $16$ numbers can be zero, or ...
1
vote
2answers
83 views

Is $2^n = p \cdot m$ solvable?

When I divide the scale between 0 and 1 continuously in halfs, are then all rational numbers (<1) covered? I.e. can every rational number $p/q (p<q)$ be written as $m/2^n$ for some $m,n \in ...
6
votes
1answer
151 views

Puzzle: Can you find an elementary proof that every $n \gt 6$ can be represented as a sum of $O(\log n)$ distinct primes?

Can you find an elementary proof that every $n \gt 6$ can be represented as a sum of $O(\log n)$ distinct primes? For example, $11 = 11$, $12 = 5 + 7$, $13 = 2 + 11$, $14 = 2 + 5 + 7$. On the other ...
1
vote
3answers
497 views

Fermat numbers and GCD

I've been working with the Fermat numbers recently but this problem has really tripped me up. If the Fermat theorem is set as $f_a=2^{2^a}+1$, then how can we say that for an integer $b$ less than $a$ ...
1
vote
3answers
147 views

GCD and relative primes

Suppose $a$ and $b$ are positive integers, and that $d=\gcd(a,b)$. Suppose we have found integers $x$ and $y$ such that $ax+by=d$. Prove that $x$ and $y$ are relatively prime.
2
votes
1answer
65 views

Are these two congruences equivalent?

Consider the following: $\forall c\in\mathbb{Z}^{+}, a \equiv b \pmod n \Leftrightarrow a \equiv b,b+n,b+2n,..,b+(c-1)n \pmod {cn}$. It seems false, so I suspect there is a typo in the statement, ...
7
votes
3answers
744 views

How to find pattern in $1,2,8,9,15,20,26,38…$ infinite sequence?

While I was investigating some specific types of prime numbers I have faced with the following infinite sequence : $1,2,8,9,15,20,26,38,45,65,112,244,303,393,560,....$ I tried to find recursive ...
-1
votes
3answers
306 views

How to show that n is a pseudoprime to the base $\hat{b}$, where $\hat{b}$ is the inverse of b modulo n?

Let $\gcd(b,n)=1$ and let $n$ be a pseudoprime to the base $b$. How to show that $n$ is a pseudoprime to the base $\hat{b}$, where $\hat{b}$ is the inverse of b modulo n? $\hat{b}$ satisfies formula ...
3
votes
1answer
481 views

How to show that $91$ is a pseudoprime to the base $3$?

The given problem: Use Lemma 2.3.3 together with Fermat's little theorem to show that 91 is a pseudoprime to the base 3. Lemma 2.3.3. Let $m_1 \dots m_r \in $ N. If $a \equiv b \pmod {m_i}$, ...
5
votes
6answers
626 views

How many number of ordered pairs $(a, b)$ where $a,b, \in \{1, 2,\ldots,100\}$ such that $7^a + 7^b$ is divisible by $5$?

How many number of ordered pairs $(a, b)$ where $a,b, \in \{1, 2,\ldots,100\}$ such that $7^a + 7^b$ is divisible by 5? I am not sure how to do this. Any ideas? EDIT: I noticed that if ...
1
vote
1answer
384 views

Number of solutions of Frobenius equation

I have one problem which needs to count the number of solution of the equation $$2x+7y+11z=42$$ where $x,y,z \in \{0,1,2,3,4,5,\dots\}$. My attempt: I noticed that that maximum value of $z$ could ...
3
votes
2answers
248 views

Does $\gcd(40,80)$ = $40$ or $20$

Which of the following correct? $\gcd(x,x\times2) = x$ or $\gcd(x,x\times2) = x/2$ I am a programmer. I am new to mathematics.
4
votes
3answers
773 views

The number of ones in a binary representation of an integer

Is there any relation that tells whether the number of ones in a binary representation of an integer is an even or an odd number?
1
vote
3answers
290 views

A question from Ireland's and Rosen's classic textbook

In the textbook "A classical introduction to modern number theory" 1990 edition, at page 22 they write that if $n>3$ then $e^{n-1}>2^n$. I am not sure I see why, I mean if $n>3$ then $e^n ...
5
votes
1answer
104 views

$\gcd(a_1x_1,\ldots,a_nx_n)$ as $x_1,\ldots, x_n$ runs through all $n$-tuples of relatively prime integers

Suppose $a_1,\ldots, a_n$ are arbitrary integers. Is there some simple way to describe the set $S$ of all possible values of $\gcd(a_1x_1,\ldots,a_nx_n)$ as $x_1,\ldots, x_n$ runs through all n-tuples ...
4
votes
1answer
188 views

A finite sum of prime reciprocals

How can you prove that $\sum\limits_k \frac1{p_k}$, where $p_k$ is the $k$-th prime, does not result in an integer?
8
votes
2answers
987 views

Why does $\phi(pq)=\phi(p)\phi(q)$?

In an RSA paper I am reading it is assumed that where $p$ and $q$ are distinct prime numbers: $\phi(pq)=\phi(p)\phi(q)=(p-1)(q-1)$ I would love to know why/how this is so? Is there some way to prove ...
1
vote
1answer
108 views

How to show that integers $x_0+\frac{m}{d}t$, $t = 0, 1,…, d-1$, are pairwise incongruent modulo m.(Hint! Antithesis.)?

Let. $m \in N, a, b \in$ Z such that $a \not \equiv 0 \pmod m$ and denote $d= \gcd(a, m)$. Suppose that $x_0 \in$ Z satisfies $ax_0 \equiv \pmod m$ How to show that the integers $x_0+(m/d)t$, $t = 0, ...
15
votes
4answers
833 views

What's the first power of two for which the most significant digit is 7?

I was just reading an anecdote about a third-grade student who was asked by her math teacher to find a number which, when two is raised to the power of that number, produces a number that starts with ...
3
votes
1answer
141 views

How to prove by induction that $a^{2^{k-2}} \equiv 1\pmod {2^k}$ for odd $a$?

Let $a \in $ Z be odd. How to prove by induction that $a^{2^{k-2}} \equiv 1\pmod {2^k}$ for all $k \geq 3$. My attempt: let $k=3$ $$\begin{align*} a^{2^{k-2}}-1&= a^{2^{3-2}}-1=a^{2}-1\\ ...
147
votes
5answers
5k views

Can you answer my son's fourth-grade homework question: Which numbers are prime, have digits adding to ten and have a three in the tens place?

My son Horatio (nine years old, fourth grade) came home with some fun math homework exercises today. One of his problems was the following little question: I am thinking of a number... It ...
4
votes
1answer
140 views

For all positive integers $n$, $14^{6n} - 11^{6n}$ is divisible by?

For all positive integers $n$, $14^{6n} - 11^{6n}$ is divisible by ? This question is followed with four options: $1)157\quad\quad 2) 163\quad\quad 3) 225\quad\quad \quad 4) \text{All ...
12
votes
1answer
261 views

If the product of $x$ positive integers is $n!$ What is the smallest possible value their sum can have?

If the product of $x$ positive integers is $n!$ What is the smallest possible value their sum can have? I was wondering what could be the most efficient strategy to solve this problem for ...
2
votes
2answers
273 views

How to show that $n$ is a prime?

Suppose that $n>1$ satisfies $(n-1)! \equiv -1 \pmod n$. Show that $n$ is a prime. (Hint: Antithesis) My own trying: $n=3$: $(3-1)!+1= 3 \cdot 1$ => $3|2!+1$. $n=5$: $(5-1)!+1=25 = 5 \cdot 5$ ...
2
votes
1answer
1k views

Proving that $n \choose k$ is an integer [duplicate]

Possible Duplicate: Proof that a Combination is an integer I can't think how to prove that ${n\choose k} \in\mathbb{Z}$. I've played with it for a while, using the factorial definition for ...
7
votes
5answers
2k views

How to prove $\log n \leq \sqrt n$ over natural numbers?

It seems like $$\log n \leq \sqrt n \quad \forall n \in \mathbb{N} .$$ I've tried to prove this by induction where I use $$ \log p + \log q \leq \sqrt p \sqrt q $$ when $n=pq$, but this fails for ...
8
votes
3answers
709 views

How to show $p_n$ $\leq$ $2^{2^n}$?

Let $p_n$ be the $n_{th}$ prime (e.g. $p_1 = 2$; $p_2 = 3$; $p_3 = 5$). Show that $p_n \leq 2^{2^n}$ for all $n$. I don't see how I can approximate the value of $p_n$. Do I need something like ...
4
votes
1answer
88 views

Proving that $n^n \notin O((n+1)!)$

How does one show that $n^n \notin O((n+1)!)$ without using limits? I've recently been trying to prove such results without limits, and this is one case that is still bothering me.
9
votes
3answers
652 views

The last two digits of $9^{9^9}$

I tried to calculate the last two digits of $9^{9^9}$ using Euler's Totient theorem, what I got is that it is same as the last two digits of $9^9$. How do I proceed further?
4
votes
4answers
545 views

Are there any other numbers like $0.999\ldots$?

In a manner similar to how the value $1$ can be represented as $0.(9)$ too, are there any other values that exhibit this property when represented in base 10?
4
votes
2answers
188 views

If $a, b, c$ and $k$ be integers, $\gcd(a,b) = 1$ and $\gcd(a, c)=k$, then $\gcd (bc, a)=k$

If $a, b, c$ and $k$ be integers, $\gcd(a,b) = 1$ and $\gcd(a, c)=k$, then $\gcd (bc, a)=k$.
3
votes
1answer
281 views

Prime congruence

If $p\equiv3\pmod{4}$ and $q=2p+1$ is a prime then $q|(2^p-1)$ if $2^p-1$ is composite. Also, prove that there are infinitely many primes $p$ for which $2^p-1$ is composite.
4
votes
2answers
240 views

What's wrong with my proof of infinitely many primes of the form $am+b$, $\gcd(a, b) = 1$

So the prof said in class that the proof of this is hard, but we might want to attempt at home. I won't be able to see him again until Wednesday, but I'm guessing there is some hole in my proof, since ...