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

learn more… | top users | synonyms

2
votes
3answers
163 views

How to simplify $42^{25\sqrt{25^{25}}}$?

Am a student preparing for GRE, I have no clue to solve this am attaching the screenshot of question: I need you give me a short cut or tip to deal such problems...
0
votes
2answers
1k views

How do I prove $\gcd(a,b) = \gcd(a+b, b)$ [duplicate]

How do I prove $\gcd(a, b) = \gcd(a+b, b)$. I know that by the euclidean algorithm, I can obtain the following equations $ax_1 + by_1 = \gcd(a, b)\tag{1}$ $(a+b)(x_2) + (b)(y_2) = \gcd(a+b, ...
2
votes
3answers
384 views

Prove that for every positive integer $n$ the number $(1−\sqrt 2)^n$ is not rational.

Prove that for every positive integer $n$ the number $(1−\sqrt 2)^n$ is not rational. Here is something I have, I'm not quite sure if I'm on the right track. Proof: Assume that $(1-\sqrt 2)^n \in ...
6
votes
2answers
286 views

For all $n>2$: there exists $p$ prime: $n<p<n!$

The question is: For all $n>2$, where $n \in \mathbb Z$: there exists $p$ prime such that $n<p<n!$ Here is my Proof: $\forall$ $p<n: p|n!$, or $p$ divides $n!$ Since $n!$ and $n!-1$ ...
1
vote
1answer
164 views

Period of a decimal expansion

Show that if n is a product of m distinct primes, then the period of the decimal expansion of 1/n is the lowest common multiple of the periods of 1/p over all primes p|n. I understand that the above ...
0
votes
0answers
69 views

Count of numbers with the given prime factors in a range [duplicate]

Given two primes: $p$ and $q$, $p \neq q$ and $n \in N$ find count of numbers $u$, so that $u \leq n$ and $u = p^k q^l$; $k, l \in N$. If we'd given with just one prime $p$ this count would be ...
2
votes
2answers
149 views

IMO 1988, problem 6

In 1988, IMO presented a problem, to prove that k must be a square if $a^2+b^2=k(1+ab)$, for positive integers a and b and k. I am wondering about the solutions, not obvious from the proof. Beside ...
1
vote
1answer
121 views

help proving this cannot be a perfect square?

Im just not really sure how to go about this. I'm assuming it involves cases where you take m and n to be x mod some number. given integers $m$ and $n$. show that $3^m+3^n+1$ cannot be a perfect ...
0
votes
0answers
65 views

A limit of floor function (a problem in number theory)

Problem. Prove that $$\large\lim_{x \to + \infty \atop\sqrt x \notin \mathbb{Z}} \left( {x^{n/2} - x^{n/2}\left| 2x^{n/2} - 2\left\lfloor x^{n/2} \right\rfloor - 1 \right|} \right)=+\infty$$ Thank ...
9
votes
4answers
371 views

Middle school number theory

Find at least three numbers that satisfy all three conditions: (1) there is a remainder of $1$ when the number is divided by $2$; (2) there is a remainder of $2$ when the number is divided by $3$; ...
4
votes
1answer
69 views

pair wise AND operation between two set of elements

I have two sets of size say $m$ and $n$. I wanted to find the sum of all pair-wise AND operation between the elements of both the sets. Suppose, if set $A=\{1,2,3\}$ and set $B=\{8,9\}$. I want to ...
1
vote
0answers
19 views

Reference for oscillation of θ(x)−x

To a question asked (in July this year) about the oscillation of θ(x)−x, Greg Martin provided the following useful response: "It is known that θ(x)−x does change sign infinitely often. I agree that ...
1
vote
2answers
42 views

problem proving this property of congruence and primes

I've been working on this for a few days and I just can't seem to find a good proof for this. Given $a \equiv b\pmod{p_i}$, $i=1,2,3,\dots,n$ and $p_i$ is prime, show that $a \equiv b ...
3
votes
2answers
111 views

How many products of two single digits $x,y$ end in a specific digit $n$ in a given base $b$?

While one can use brute force (i.e. counting a multiplication table) to see that e.g. in base ten there are 27 combinations yielding zero ($0\cdot n, 2n\cdot 5$ and the other way around, counting ...
0
votes
0answers
22 views

A question about the order of $2$ in the reduced residue system of a $\frac{p\#}{2}$ where $p\#$ is the primorial of $p$

I've noticed a pattern in the order of $2$ in the reduced residue system for $\frac{p\#}{2}$ where $p\#$ is the primorial for a prime $p$. For $\frac{3\#}{2}$, $\operatorname{ord}_{3}(2)=2$ and ...
2
votes
2answers
4k views

Why are prime numbers important in real life? [duplicate]

What practical use are prime numbers? Why do we emphasise the teaching of prime numbers?
10
votes
1answer
941 views

Would proof of Legendre's conjecture also prove Riemann's hypothesis?

Legendre's conjecture is that there exists a prime number between $n^2$ and $(n+1)^2$. This has been shown to be very likely using computers, but this is merely a heuristic. I have read that if this ...
3
votes
2answers
106 views

Choosing $15$ out of $100$ whole numbers with difference of any $2$ divisible by $7$

How can we prove with the pigeonhole principle that having $100$ whole numbers, one can choose $15$ of them so that the difference of any $2$ is divisible by $7$?
3
votes
2answers
77 views

Euclidean Algorithm

The question is to find $2$ integers $a$,$b$ $\in \mathbb{Z}$ for which when applying the Euclidean Algorithm for finding the $\gcd \left(a,b\right)$ precisely $10$ steps are required. This is what I ...
3
votes
1answer
175 views

How to show that every integer greater than $23$ is the sum of two squareful numbers?

How to show that every integer greater than $23$ is the sum of two squareful numbers? I checked up to $50000$. The argument I used in this answer to a similar problem doesn't work because it would ...
6
votes
2answers
159 views

Find integers s and t such that $1=7 \times s+11 \times t$. Show that s and t are not unique

Find integers s and t such that $1=7 \times s+11 \times t$. Show that s and t are not unique. I understand why s and t are not unique, I am just unsure how to prove it. Thank you!
1
vote
3answers
113 views

If n and 6 are relatively prime numbers then prove that $n^2-1$ is divisible by 24

I only proved that it's divisible by 12, I am missing another factor of 2.
1
vote
1answer
68 views

Can we restrict the average multiplicative order of a number?

We are given a size of a number system, $s$, which is the number of components in the system. For example, the quaternions have $s=4$ components. Now, in general, we will be interested in ...
0
votes
0answers
42 views

If $a$ and $b$ are positive integers, then $ab=\mathrm{lcm}(a,b)\cdot\gcd(a,b)$ [duplicate]

I have been phased with a homework problem. Show that if $a$ and $b$ are positive integers, then $ab=\mathrm{lcm}(a,b)\cdot\gcd(a,b)$ Thank you for your input!
1
vote
1answer
116 views

Count of distinct multiples of n numbers

Let $A=\{a_1,\ldots,a_n\}$ where $a_i < a_{i+1}$ and a large number $K$ such that $a_n < K$. How do I count the total number of distinct multiples $<K$ for all elements of $A$? For example, ...
0
votes
2answers
112 views

Prove the following divisibility statements without use of induction

(a) $5$ $|$ $3^{3n+1}+2^{n+1}$ (b) $21$ $|$ $4^{n+1} + 5^{2n-1}$ (c) $24$ $|$ $2 \cdot7^n + 3 \cdot5^n - 5$ These are trivial by using induction. But I have tried to prove it by binomial theorem and ...
1
vote
1answer
165 views

Relatively prime numbers

Find the number of elements in the set $\{m:1\le m\le 1000,m$ and $1000$ are relatively prime$\}$. My attempt: We are to find the number of elements which have only $1$ as the common factor with ...
1
vote
1answer
89 views

When is $(a-1)(a-b)/b$ a positive integer?

Let $a,b \geq 1$ be positive integers and $S \subset \mathbb{N}^2$ where $$ S = \{(a,b)\in\mathbb{N}^2 : (a-1)(a-b)/b \text{ is a positive integer} \}. $$ How does one go about determining all the ...
1
vote
2answers
115 views

Representing an Integer as a Sum of at Most $k$ Triangular Numbers

What is the smallest $k$ such that every $n \in \mathbb{N}$ can be represented by a sum of exactly $k$ triangular numbers? For the sake of simplicity, I will assume $0$ is a triangular number. I've ...
2
votes
1answer
182 views

Difference sets avoiding quadratic residues

I have a homework question that is stumping me, and I am looking for an entry point. It goes like this: Suppose $p$ is prime. Prove that the largest set $S\subseteq\{0,1,\dots, p-1\}$ such that ...
0
votes
2answers
123 views

Show $[a]_m=[a]_n\cup[a+m]_n\cup\dots\cup[a+m(k-1)]_n$

Let $m$ and $n$ be positive integers such that $m|n$. Show that for any integer $a$ the congruence class $[a]_m$ is the union of congruences $[a]_n,[a+m]_n,[a+2m]_n,\dots,[a+n-m]_m$. Which is just ...
0
votes
0answers
32 views

How quickly can we find a modulated sequence of powers?

How quickly can we find an element of (at least) multiplicative order at least $p$, where $p \in \mathbb{N}$? The complete question is that we start with a number system of $s$ elements; for example ...
4
votes
4answers
136 views

Prove that $\log_{36} 30 $ is irrational number.

Prove that $\log_{36} 30 $ is irrational number. We can suppose that $\log_{36} 30 $ is rational number. So we have that $\log_{36} 30 = \frac{p}{q}$ where $\gcd(p,q) = 1$. By definition of logarithm ...
8
votes
4answers
329 views

Idea of the Proof : Existence of a & b so that (Any integer greater than 8) = 3a + 5b [duplicate]

Claim: Prove that for every integer $n \geq 8$, there exist nonnegative integers $a$ and $b$ such that $n = 3a + 5b.$ Proclaimed solution : Let $n ∈ \mathbb{Z}$ with $n ≥ 8.$ $\text{ Then } n ...
0
votes
1answer
55 views

Ambiguous definition of the set of Natural Number [duplicate]

According to the book "An introduction to the analysis of algorithms (written by Michael Soltys)", the author says in chapter 1 as follows. Let $\mathbb N = \{0, 1, 2,...\}$ be the set of natural ...
3
votes
2answers
72 views

Sum of two squares modulo a prime in $4\mathbb Z + 1$

I am trying to find the number of solution of the equation $$ x^2 + y^2 = 1 $$ in $\mathbb Z/p\mathbb Z$, where $p$ is a prime such that $p\in4\mathbb Z+1$. Apart from the trivial solutions $(0,\pm ...
5
votes
1answer
138 views

The number of solutions to $\frac{1}x+\frac{1}y+\frac{1}z=\frac{3}n,x,y,z\in\mathbb N$

Denote $$g(n)=\{\{x,y,z\}\mid \frac{1}x+\frac{1}y+\frac{1}z=\frac{3}n,x,y,z\in\mathbb N\},$$ $$h(n)=\{\{x,y,z\}\mid \frac{1}x+\frac{1}y+\frac{1}z=\frac{3}n,1\leq x\leq y\leq z,x,y,z\in\mathbb N\},$$ ...
2
votes
2answers
162 views

Show that this set of integers can be expressed in the form $7r+10s$ with $r, s$ non-negative integers.

The set of integers are: ${54,55,...,60}$ I am having trouble with the non-negative integers part, otherwise the question appears to be quite simple. I have that since $gcd(7,10) = 1$, by extended ...
2
votes
4answers
85 views

Proof that $3 \mid \left( a^2+b^2 \right)$ iff $3 \mid \gcd \left( a,b\right)$

After a lot of messing around today I curiously observed that $a^2+b^2$ is only divisible by 3 when both $a$ and $b$ contain factors of 3. I am trying to prove it without using modular arithmetic ...
1
vote
2answers
65 views

Prove that if $n$ is coprime to $10$ then $n^{101} \equiv n \pmod{1000}$

"Prove that if $n$ is coprime to $10$ then $n^{101} \equiv n \pmod{1000}$" I know that this has something to do with Euler's function, but i'm not sure how to apply it. A fellow on an IRC channel ...
6
votes
3answers
143 views

Solve $2^n=k^2+k+2$ for positive integers

This problem came from my own research ( research for fun, not professional ). I was able to simplify a little and solve some special cases, but I need a help to get the general case which is "Find ...
0
votes
1answer
52 views

Relation between $a$ and $a^{-1}$ in integer rings about evenness

Could I ask something seemingly simple? Well, let $N$ be a positive odd number (the reason why I set $N$ to be odd is I could actually solve the problem when $N$ is even which is easy) and $a$ is an ...
2
votes
2answers
140 views

$n$ is a natural number such that $n^5$ is odd

$n$ is a natural number such that $n^5$ is odd then which of the following is true? $1.n$ is odd $2.n^3$ is odd $3.n^4$ is even. $3$ is always true as any number multiplied by even times it will ...
10
votes
3answers
242 views

Math contest proof problem fractions

Could someone help me with this? Let $x, y, z$ be positive integers with greatest common divisor $1$. If $\frac 1 x +\frac 1 y=\frac 1 z$, then show that $\sqrt{x + y}$ is an integer.
3
votes
3answers
130 views

Probability for the sum of two random numbers being a prime number?

Suppose $N$ is a (large) fixed positive integer, and one is asked to randomly choose any two integers (numbers could be same as well) from $1$ to $N$ (including $1$ and $N$). Let the experiment be ...
1
vote
6answers
303 views

Prove that there are infinitely many natural numbers that can't be written as $a^2+p$

Generally speaking, if they ask us to prove that there are infinitely many numbers that can't be written in a certain way, how should we try to solve the problem? I've never seen a solution to such a ...
2
votes
0answers
64 views

show $\frac{n}{d}$ is the additive order

Prove that if $n>1$ and $a>0$ are integers and $d=gcd(a,n)$ then the additive order of $a\pmod{n}$ is $\frac{n}{d}$. *Additive order is the smallest positive integer that satisfies $ax\equiv ...
7
votes
2answers
244 views

Show that the sequence $1,2,3,4,5,6,7,8,9,1,0,1,1,1,2,1,3,1,4,1,5,1,6,1,7,1,8,1,9,2,0,2,1,\cdots$ isn't periodic

Show that the sequence $\{a_n\}_{n\in \mathbb{N}} = \{x: x=$ the nth decimal digit of Champernowne's constant$\}$ is not periodic. For those who don't know what Champernowne's constant is, it's the ...
0
votes
1answer
80 views

A problem regarding the proof of ${p^nk\choose p^n}\equiv k\mod p$, where $p\nmid k$.

In this proof, there is a statement where: $$(a+b)^{p^nk}\equiv (a^{p^n}+b^{p^n})^k\mod p$$ I understand this part. But then it expands both sides binomially, and compares coefficients of ...
1
vote
2answers
82 views

'Coprime' problem related to integer rings

I am handling a problem involving the proof of whether two integers are coprime or not. Think of a positive integer $N$ and two integers $r$ and $s$ in $\mathbb{Z}_N$ such that $\gcd{(N, r)}=1$ and ...