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

learn more… | top users | synonyms (1)

1
vote
2answers
50 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
55 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 ...
0
votes
2answers
48 views

Properties of Euler's phi function

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
0answers
67 views

Solve the diophantine equation $x^n-y^n=1001$

For all $n \in \mathbb{N}$ solve the diophantine equation $x^n-y^n=1001$, $ x,y \in \mathbb{N}$. The cases $n=1,2$ are trivial ones. But for $n>2$ I cant find any sulutions. How to prove that ...
1
vote
1answer
14 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
18 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
29 views

How to Establish the following sum notation

Establish the following sum notation $\sum_{i=1}^{n}(a_i+b_i)$=$\sum_{i=1}^{n}a_i+$$\sum_{i=1}^{n}b_i$ my 2 tries my first try i use 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
31 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
19 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
31 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
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
146 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
49 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
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
47 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
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
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 ...
-3
votes
5answers
215 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
40 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
47 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.