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

learn more… | top users | synonyms (1)

0
votes
0answers
23 views

Prove: If $p \in \mathbb{N}$, $p$ is prime and $p\mid ab$ then $p\mid a$ or $p\mid b$. [duplicate]

Theorem 1. If $p \in \mathbb{N}$, $p$ is prime and $p\mid ab$ then $p\mid a$ or $p\mid b$. I am stuck on this proof here is what I have done so far: Proof of Thm 1. $p\mid ab \implies ...
0
votes
1answer
17 views

Find the number of possible values of $a$

Positive integers $a, b, c$, and $d$ satisfy $a > b > c > d, a + b + c + d = 2010$, and $a^2 − b^2 + c^2 − d^2 = 2010$. Find the number of possible values of $a.$ Obviously, factoring, ...
1
vote
1answer
19 views

A question about $\gcd$ and divisibility

Let $\sigma$ be the classical sum-of-divisors function. Suppose that I have the following equations: $$2n^2 - \sigma(n^2) = \frac{\sigma(n^2)}{q^k}\cdot{\sigma(q^{k-1})}$$ $$2n^2 - \sigma(n^2) = ...
3
votes
1answer
19 views

What is $\gcd(\sigma(q^{k-1}), \sigma(q^k))$?

Let $\sigma$ denote the classical sum-of-divisors function. What is $\gcd(\sigma(q^{k-1}), \sigma(q^k))$? Update: I have transferred the transcript of my attempt to an actual answer to this MSE ...
0
votes
1answer
15 views

How many rows & columns do 1,028 equal spaces create…

I have a board that is 17.5" wide and 67" long. I need to divide this board into 1,028 equal spaces. How many rows and how many columns will this equate to?
5
votes
1answer
50 views

How can I prove the Carmichael theorem

I am trying to prove that these two definitions of Carmichael function are equivalent. I am using this definition of Carmichael function: $\lambda(n)$ is the smallest integer such that ...
1
vote
4answers
62 views

$6^{66}\equiv r \pmod {66}$

The answer doesn't need to be exact, the possible answers to the exercise are "between 30 and 40", "from 50 to 66" or something akin to that. I've no idea how to solve this. Previous problems of this ...
1
vote
2answers
35 views

Prove: $\gcd(n^a-1,n^b-1)=n^{\gcd(a,b)}-1$ [duplicate]

I'm trying to prove the following statement: $$\forall_{a,b\in\Bbb{N^{+}}}\gcd(n^a-1,n^b-1)=n^{\gcd(a,b)}-1$$ As for now I managed to prove that $n^{\gcd(a,b)}-1$ divdes $n^a-1$ and $n^b-1$: Without ...
0
votes
1answer
24 views

General question on notations when dealing multiplicative and additive modulo

One of the property for the requirement for a set to be a group is associativity. Under ordinary multiplication: $\large{a(bc)=(ab)c}$ Under ordinary addition: $\large{a+(b+c)=(a+b)+c}$ What ...
5
votes
1answer
29 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
20 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
1answer
30 views

Show that the set $\{1,2,\ldots, n-1\}$ is a group under $\bmod n$ IFF $n$ is prime.

So I need to show that this set, together with the operation of multiplication mod $n$, is a group if, and only if, $n$ is prime. What would be the best way to proceed? proof by contradiction? (i.e. ...
4
votes
1answer
33 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
49 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
35 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
65 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
61 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
34 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 ...
3
votes
2answers
114 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
22 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
31 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
43 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
33 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
21 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
82 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
51 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
42 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
41 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
62 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
14 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
50 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
32 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 ...