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

learn more… | top users | synonyms (1)

-3
votes
1answer
30 views

Revised proof for the set of positive irrational numbers closed under multiplication*

The set S of positive irrational number is closed under multiplication (denote *) if the product of an ordered pair of element of S is also an element of set S. To show that the set S is not closed, ...
0
votes
5answers
74 views

A better proof for the set of irrational number not closed under ordinary multiplication.

A positive irrational number $$q$$ is by definition a real number than cannot be expressed as a ratio of $2$ integers. To show that the set of irrational number is not closed under ordinary ...
0
votes
1answer
27 views

Show that the set $\mathbb{Q}^+$ is a group under ordinary multiplication

To be a group, a set with a binary operation has to satisfy all four of the group axioms. My problem is with closure as each time I am unsure if my proof suffices. The set of positive rational numbers ...
4
votes
3answers
143 views

Numbers with 2015

I like to build math problems; to solve the one below I should first find a certain square and use it in my solution. I would want to know if anyone can solve this problem otherwise. Thanks. ...
0
votes
1answer
23 views

Stuck on proving two quite simple results using modular arithmetic and factors.

Hello I'm trying to do two problems but can't seem to get the proofs myself, any help is appreciated. I know the definitions of congruence, definition of a factor and Bezout's lemma I've tried using ...
0
votes
3answers
27 views

If $A|B$ and $B|A$ then prove $A=\pm B$ [duplicate]

If $A|B$ and $B|A$ then prove $A=\pm B$ So far I have $A|B \iff AX=B$ and $B|A \iff BY=A$ with $X,Y \in \mathbb{Z}$ Not sure how to finish, any help.
2
votes
2answers
46 views

Prove that $a^{p^2}\equiv a^p\pmod{p^2}$ for every $a\in\mathbb{Z}$

Question: Prove that $a^{p^2}\equiv a^p\pmod{p^2}$ for every $a\in\mathbb{Z}$ First note that when $p$ is prime and $1\leq r\leq p-1$ the binomial coefficient $$\binom{p}{r}=\frac{p!}{r!(p-r)!}$$ is ...
2
votes
0answers
42 views

can you help me to solve this equation in antural numbers set?

Can you help me find the natural solutions of $$2^x+3^y=5^z$$ or can you introduce a book that talk about these equations?
0
votes
2answers
41 views

Confusion with $O$ function

I read this identity in lecture notes and need help understand ing the $O$ function $$\sum_{1\leq d\leq x}\mu(d)\cdot \frac{1}{2}\left\lfloor\frac xd\right\rfloor\left(\left\lfloor\frac ...
0
votes
2answers
22 views

Finding the GCD of two polynomials.

Hello I'm trying to find the GCD of these two polynomials: $$X^4-X^3-4X^2-X+5$$ $$X^2+X-2$$ And then I want to express the GCD of these two polynomials in terms of themselves multiplied by other ...
3
votes
2answers
33 views

$\forall n\ /\ \not\exists$ {primitive roots modulo n}: if $\ Max(ord_n(k))+1 \mid n\ $ then $\ Max(ord_n(k))+1\ $ is prime?

When a number $n$ does not have primitive roots modulo n, $Pr(n)$, it is possible to generate the set $M$ of those numbers $m$ whose order $ord_n(m)$ is the maximum multiplicative order of $k$ in ...
3
votes
2answers
41 views

Divisors of a product.

Is there a proof that if $d \mid mn$, where $m$ and $n$ are coprime, then $d=d_1d_2$ where $d_1 \mid m$ and $d_2 \mid n$, where the $d_i$ are comprime? I was working on Project Euler and came across ...
2
votes
2answers
43 views

What do the symbols $\mathbb{Z}$ and $\mathbb{Z}_n$ mean on this discrete math problem? [on hold]

Currently I have come across a problem set which I cannot decipher or begin to ask or search because I do not know what kind of notation or problems these are. Please circle the best description: ...
0
votes
2answers
58 views

Triangle whose side lengths and area are rational numbers [on hold]

Does there exist a triangle with side lengths given by rational numbers $x$, $2x$, and $y$ such that the triangle's area is also rational number?
2
votes
1answer
13 views

Bound on Lynden words made of $q$ letters

Let $N(q,n)=\frac{1}{n}\sum_{d|n}\mu(n/d)q^d$ for $q$ positive integer. Is it true that $N(q,n)<q^n/n$? This is true for $q$ prime which corresponds to the number of monic irreducible polynomials ...
2
votes
2answers
44 views

Prove that $12 \mid m \iff$ both $6 \mid m$ and $4 \mid m$.

Give a formal proof to the following theorem which I do not know where to start. Theorem: For all natural numbers 'm', 12 divides m only if 6 divides m and 4 divides m.
0
votes
2answers
19 views

How to solve this linear congruence equation? [on hold]

How to solve this linear congruence equation? How to solve $6x \equiv 5 \mod 14$?
2
votes
3answers
20 views

Is Bezout's lemma enough to confirm the HCF of a number.

Is Bezout's lemma enough to confirm the HCF of a number? So suppose we have $$ax+by=z$$ does this mean $$hcf(a,b)=z$$
0
votes
2answers
31 views

Show that if $p$ is a prime and $p \in (n, 2n]$, then $p \mid {2n \choose n}$.

I'm having a problem understanding the answer to this question below. The step I don't get is underlined in red. I understand everything else just the red underline I am stuck on. Sorry I am a ...
2
votes
1answer
45 views

Average of elements in a subset of $\{1,2,3,..,n\}$ is greater than $\frac{n+1}{2}$ [on hold]

Consider two integers $n \ge m \ge 4$ and $A=\{a_1,a_2,...,a_m\}$ a subset of the set $\{1,2,3,...,n\}$ with the property that $$\forall a,b \in A \text{ with } a \neq b, \text{ if } a+b \le n, \text{ ...
1
vote
1answer
51 views

$\binom{p}{i}$ divisible by $p$, with $p$ prime

Let $p$ be a prime. How do you show that the binomial coefficients $\binom{p}{i}$ are divisible by $p$ for $1\leq i\leq p-1$? And how does this result in the congruency $(x+y)^p\equiv x^p+y^p\pmod p$ ...
1
vote
1answer
31 views

Prove that the solutions to the system of equations are integers

Let $a, b \in \mathbb{Z}$ and consider the system of equations below: $$\begin{cases} y -2x-a =0\\ y^2-xy+x^2-b=0\end{cases} $$ Prove that $x,y\in\mathbb{Q}$ implies $x,y\in\mathbb{Z}$. I ...
2
votes
2answers
37 views

Given that $1 = 27 \times 11 - 74 \times 4$, solve the following equations in modulo $74$: $ 3x - y = 1$; $2x + 3y = 0$

Given that $1 = 27 \times 11 - 74 \times 4$, solve the following equations in modulo $74$: $3x - y = 1$; $2x + 3y = 0$. Thank you.
0
votes
1answer
25 views

Prove that $ax \equiv 1 \bmod n \implies \gcd(a,n) = 1$.

I'm trying to prove the following but having difficulties. Suppose $a,x \in \mathbb{Z}$ and $n \in \mathbb{N}$ then prove if $ax \equiv 1 \mod n$ then $a$ is coprime to $n$. I know what it ...
2
votes
1answer
44 views

Suppose $m \mid 2^p - 1$. Show that $m \equiv 1 \pmod {2p}$.

I would like to get help with this proof: Let $p\ge3$ be a prime number, and let $m$ be a divisor of $2^{p}-1$, Prove that $m\equiv 1\ (mod\ 2p)$. I thought about proving that $m=1\ mod\ p$, ...
1
vote
0answers
83 views

$ x^2+y^2+z^2=k(xy+yz+zx) $

Let $A $ be a set of all positive integers so that if $ n\in A $ then $n-1$ has at least one prime divisor $p\equiv 2( mod 3)$ such that $v_p(n-1)$ is odd and let $B$ be a set of all positive ...
3
votes
1answer
47 views

Wilson's Theorem proof

How do I prove Wilson's Theorem $$\large{(p-1)! \equiv -1 \pmod p}$$ using Euler's theorem $$ \large{a^{\phi(n)} \equiv 1 \pmod n }$$ where $ \large{\phi(n)} $ denotes Euler's Totient function? ...
4
votes
1answer
44 views

Is there a counterexample? $\forall p \in \Bbb P\ ,\ p\gt 61\ ,\ \exists\ r1,r2\ \in \{\ Primitive\ Roots\ Modulo\ p\ \}\ /\ r1+r2 = NextPrime(p)$

This is the weirdest thing I have observed so far! Take the set of Primitive Roots Modulo p (link to definition here) of a prime number $p$, $Pr(p)$. For those primes $p \gt 61$ there is always a pair ...
6
votes
0answers
33 views

Infinite solutions for $(\frac{n+1}{n})^a\cdot (\frac{m+1}{m})^b = 2$

Given $(\frac{n+1}{n})^a\cdot (\frac{m+1}{m})^b = 2$ where a, b, n, and m are all positive integers, are there infinitely many solutions $(a,b,n,m)$?
0
votes
1answer
25 views

Is it possible to exhibit a collection of sets

Let a subset $D$ of the natural numbers be called convergent or divergent when the associated series $\sum_{d \in D} \frac{1}{d}$ converges or diverges. Define a topology on $\Bbb{N}$ by defining the ...
0
votes
0answers
20 views

Counting the number of elements $x$ between $p$ and $p^2$ where lpf$(x(x+2))=7$

Let $p > 7$ be any prime. Let $f_7(p)$ be a function that counts the number of elements $x$ where $p < x < p^2$ and lpf$(x(x+2))=7$ where lpf is the least prime factor. It has been ...
6
votes
2answers
75 views

When is the sum of divisors a perfect square?

For $n=3$, $\sigma(n)=4$, a perfect square. Calculating further was not yielding positive results. I was wondering is there a way to find all such an $n$, like some algorithm? We know that if ...
2
votes
1answer
31 views

Questions on integer-valued polynomials

An integer-valued polynomial or numerical polynomial is a polynomial $f \in \mathbb Q[x]$ with the property that $f(\mathbb Z)\subseteq \mathbb Z$. The set of numerical polynomials forms a subring ...
-3
votes
5answers
213 views

What is zero? Irrational or rational or it have both the properties? [duplicate]

We say, A number is rational if it can be represented as $\frac{p}{q}$ with $p,q \in \mathbb Z$ and $q\neq 0$. Any number which doesn't fulfill the above conditions is irrational. What ...
4
votes
1answer
39 views

A functional equation with no term outside functions

Find all $f:\mathbb{N} \rightarrow \mathbb{N}$ satisfying $$f(m-n+f(n))=f(m)+f(n)$$ for all $m,n \in \mathbb{N}.$ I have no idea about how to find them, because there are no terms outside of the ...
1
vote
1answer
33 views

Solving the congruence $3x^2 + 6x + 1 \equiv 0 \pmod {19}$

I tried to solve this equation but without a success: $3x^{2}+6x+1 \equiv 0 \pmod {19}$ I concluded hat $x(x+2)\equiv 6 \pmod{19}$, the only way i think to solve this is by just trying all the ...
2
votes
0answers
44 views

Need help in understanding the question. Elemntary number theory

I have this question in my home assignment. I contains two parts and I don't quite understand what is the difference between them.The question is: Let $n > 2$ be an integer such that ...
4
votes
2answers
27 views

Question about proof of Lucas Primality test

Lucas Primality Test. Suppose that $n > 1$ and $a$ are integers with $a^{n-1} \equiv 1 \mod n$ and $a^{(n-1)/p} \not\equiv 1$ for all primes $p \mid n-1.$ Then $n$ is prime. Proof. Suppose that ...
0
votes
2answers
33 views

Why having $ma+np=1$ implies that $m$ is the inverse?

I'm reading Stilwell's: Elements of Number Theory. In here: I don't understand why having $ma+np=1$ implies that $m$ is the inverse.
5
votes
3answers
124 views

Factoring product of two primes from solutions of congruence

The algorithm purposed to play a fair game of heads or tails over the phone given here claims that knowing the four solutions to $$ x^2 \equiv a^2 \pmod n$$ would allow us to factor $n$ where $n$ is ...
1
vote
1answer
45 views

Prove or disprove: If $a^2 \mid bc$, then $a \mid b$ or $a \mid c$

Prove or disprove: If $a^2 \mid bc$, then $a \mid b$ or $a \mid c$. I have not been able to find a counter example so I am thinking it may be true. I started by thinking that since $a^2 \mid bc$, ...
0
votes
0answers
43 views

Reduction of trigonometric functions to $x$ power [on hold]

$$\huge{(\sqrt{1 - \sin^2x})^{2^{x^\sqrt{1 - \sin^2x}}}}$$ $x > 0$ if the domain of $x$ is between $1$ and $1.5$
1
vote
2answers
55 views

Let $m = 4^n+1$ for some integer $n \geqslant 1.$ Prove that $3^{(m-1)/2} \equiv -1 \pmod m$ if and only if $m$ is prime.

Let $m = 4^n+1$ for some integer $n \geqslant 1.$ Prove that $3^{(m-1)/2} \equiv -1 \pmod m$ if and only if $m$ is prime. $(\mathbb{Z} / m \mathbb{Z})^{\ast} =$ unit group modulo $m.$ Suppose that ...
2
votes
1answer
23 views

Find the first Poulet number

A Poulet number (OEIS $A001567$) is called a composite number $n$ such that $2^{n-1}−1$ is divisible by $n$. The first such a numbers are: $$ 341, 561, 645, 1105, \ldots $$ Question: How to prove ...
4
votes
1answer
27 views

$x-1$ in base $x$ counting systems

Please excuse the lack of expertise. I'm not a mathematician, nor have I studied it since high school. I was thinking about how all the digits of multiples of $9$ summed equal a multiple of $9$. I ...
0
votes
2answers
33 views

For which primes $p \ne 2,5$ does the congruence $x^2 \equiv 10 \mod p$ have a solution?

For which primes $p \ne 2,5$ does the congruence $x^2 \equiv 10 \mod p$ have a solution? Using the Legendre symbol, we have $\left(\dfrac{10}{p}\right) = \left(\dfrac{5}{p}\right) ...
1
vote
2answers
24 views

Sequence of perfect squares

Let $a,b\in \mathbb{N}$. Prove that, if $a$ is quadratic residue modulo $b$, then sequence $(a+kb)$, $k\in \mathbb{N}$, has infinite amount of perfect squares. How should I approach this ...
2
votes
6answers
97 views

Prove that $7$ divides $1 + 2^{(2^n)} + 2^{(2^{n+1})}$ by induction

Prove that $7$ divides $1 + 2^{(2^n)} + 2^{(2^{n+1})}$ by induction. I ran into the above problem. The base case $n=1$ gives $21$ which is divisible by $7$. Now assume it is true for $n$. Then for ...
0
votes
1answer
48 views

Problem with Recurrence Relations

A particle P executes a random walk on the line above such that when it is at point $n$ ($1 \leq n \leq 9$, $n$ a non-negative integer), it has a probability of $0.4$ of moving to $n+1$ and a ...
0
votes
1answer
20 views

Counting the spokes

I’ve been playing around with wheel factorization (Wikipedia link) and wanted to know how many spokes there are in a given wheel. For a 2-7 wheel the circumference of this would be 210 and then I can ...