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

learn more… | top users | synonyms (1)

4
votes
0answers
12 views

Remainders of quadratic trinomial

The problem is to determine, whether there exist a quadratic trinomial $f(x) = ax^2 + bx +c$ with integer coefficients (with $a$ not a multiple of 2014), such that the numbers $\ f(1), \ f(2),\, ...
1
vote
0answers
7 views

Prove that one eight of Gauss circle problem counts integer sided acute triangles with largest side n.

In the OEIS there is the sequence A247588 starting: 1, 2, 3, 5, 6, 8, 11, 13, 15, 17, 21, 25, 27,... It has the name "Number of integer sided acute triangles with largest side n." Let $a(n)$ be that ...
0
votes
0answers
11 views

Show that the set {1,2,…n-1} is a group under mod(n) IFF n is prime.

So I need to show that this set is a group IFF multiplicative mod(n) where n is prime. Would letting n be some non-prime, I.e., n=10 and demonstrating via proof by contradiction the best way to ...
4
votes
1answer
23 views

What are statements about the natural numbers where induction is impossible or unnecessary to prove?

I'm looking for statements like "for all natural numbers, ____" where induction would be impossible or unnecessarily complicated. This is for pedagogical reasons. When students first learn induction, ...
0
votes
2answers
39 views

solve $b^2c-a^2=d^3$ with some conditions.

Solve $b^2 c-a^2=d^3$ Conditions $b^2c>a^2$,  $b$>0, $c$>0,  $a$, $b$, $c$, $d$ are rational number. Example Solution $a=108$, $b=12$, $c=849$, $d=48$ Is Solving this equation impossible?
-1
votes
2answers
31 views

Difference between $A \equiv B \pmod {n}$ and $A \pmod {n}$

In terms of definition and ideas, what is the difference between saying $$A \equiv B \pmod n$$ and $$A \pmod n$$?
2
votes
2answers
60 views

Find the smallest number divisible by $204$ the digits of which sum to $204$

The problem asks us to find the smallest number divisible by $204$, with sum of its digits equal to $204$. I totally don't know what to use here. I would be thankful for any hint that would enable ...
2
votes
3answers
57 views

Evaluate $7^{8^9}\mod 100$

I'm preparing myself for discrete math exam and here's one of the preparation problems: Evaluate $$7^{8^9}\mod 100$$ Here's my solution: $7^2\equiv49 \mod 100\implies (7^2)^2\equiv49^2=2401\equiv ...
2
votes
2answers
60 views

Properties of Euler's phi function [on hold]

If $\phi(n) =n-2$ then $n=4$. I need a hint to prove this statement. "This is my first Number Theory course."
1
vote
3answers
33 views

If $n$ is a natural number and $n$ is a $4th$ power and a $5th$ power prove it is a $20th$ power.

If $n$ is a natural number and $n$ is a $4th$ power and a $5th$ power prove it is a $20th$ power. (Hint: Use fundamental theorem of arithmetic). I can't do this problem and am looking for ...
1
vote
1answer
93 views

Solving the Diophantine equation $x^n-y^n=1001$

For all $n \in \mathbb{N}$, solve the Diophantine equation $x^n-y^n=1001$, where $x,y \in \mathbb{N}$. The cases $n=1,2$ are trivial ones. But for $n>2$ I can't find any solutions. How could I ...
1
vote
1answer
16 views

How does the fundamental theorem of arithmetic / primality tests apply to GCDs?

I've been asked to calculate gcd(1962,1524) which I found to be 6. Now I'm asked to 'Verify your answer using primality tests and the fundamental theorem of arithmetic I'm struggling to see how I ...
1
vote
1answer
19 views

Properties of Jacobi symbol

Let $\left(\frac{a}{n}\right) $ be Jacobi symbol . It is well known that Jacobi symbol for $a=-1$ and $a=2$ satisfies the following: $\left(\frac{-1}{n}\right) = \begin{cases} 1, & \text{if } n ...
2
votes
2answers
30 views

How to establish the distributive property of sum notation

Establish the following property of sum notation: $$\sum_{i=1}^{n}(a_i+b_i) = \sum_{i=1}^{n}a_i + \sum_{i=1}^{n}b_i$$ I have tried in two ways. My first try uses recursive induction: ...
1
vote
1answer
42 views

Finding the order of 3 modulo 242

I know from Euler's theorem that \begin{equation*} 3^{110} \equiv 1\mod 242 \end{equation*} because \begin{equation*} \phi(242) = 110. \end{equation*} However to find the order of $3$, I need to find ...
0
votes
2answers
32 views

How to find kth smallest value of a linear equation

Here's a question that was asked in IOITC 2009 India. Even though it should have a solution related to algorithms, yet I post it here as it is pretty "number-theoretic". Indraneel loves posing ...
0
votes
1answer
20 views

Arithmetic modulo $n$ when $n>a$

$r=a \pmod n$ can be rewritten as $a = qn + r$ where $a$ and $n$ are positive and non-zero integers and $q$ is a unique integer. When solving for $a \pmod n$ such that $a$ is greater than $n$, it is ...
-3
votes
1answer
33 views

Revised proof for the set of positive irrational numbers closed under multiplication* [on hold]

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
77 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
29 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
150 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
48 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
50 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
23 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
36 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
42 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
60 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
48 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
45 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
90 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
48 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
45 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 ...