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

learn more… | top users | synonyms (1)

2
votes
2answers
46 views

statements including Mobius Inversion Formula

Find a simple formula for $f(n) = \sum \limits_{x|n} \mu(x) \tau(x)$ $f(n) = \sum \limits_{x|n} \sigma(x) \mu(n/x)$ which I believe is equal to n. $f(n) = \sum \limits_{x|n} \mu(x) \mu(n/x)$. ...
1
vote
2answers
37 views

Relevance of prime being divisble by $4k+1$ in proof that 'There are infinitely many primes of the shape $4k+3$'

Show that there are infinitely many primes of the shape $4k+3$ Proof: $1)$ Suppose that there are only finitely many such primes, say $p_1,...p_n$. $2)$ Consider the integer $Q=4p_1...p_n-1$ $3)$ ...
0
votes
1answer
26 views

Simple question in number-theory

$a, b, c$, and $d$ are integers. From exactly one of the equations $A, B, C, D, E$, one can deduce that $14$ divides $a \cdot b$. Which one? A) $7a+8b=14c+28d$ B) $14a+28b=7c+8d$ C) ...
0
votes
2answers
26 views

Converse of Bézout's identity

Given that we know gcd$(a,b)=sa+tb$ where $s,t \in \mathbb Z$, I wonder is the converse true? I.e., can we say that the value of $ax+by$ is the gcd of any $2$ of $a,x,b,y$?
0
votes
2answers
30 views

Solving an inequality involving a floor

Increasing the integer $k$, I can make the floor of $L/k$ smaller than $r$: $$\left\lfloor \frac{L}{k} \right\rfloor \lt r$$ where $L, k, r$ are positive integers, $k\leq \lfloor \frac{L}{2} ...
1
vote
0answers
40 views

Multiple of power of 5 with only the digits 2,5,6

after helping a friend solve a homework, I asked myself the following question: $H\subseteq\{1,2,\ldots,9\}$, $T(H)=\{n\in\mathbb{N}:$ all the digits in the decimal representation in $n$ belong to ...
3
votes
1answer
31 views

Proving the equivalence of a finite set

Let A be a finite set. Prove that if A≈􏰔n and A≈􏰔m, then n=m. The answer in the book uses a max function, so I was just wondering if there was a simpler way. If not, it would be appreciated if ...
1
vote
1answer
21 views

Given $2^n$, what is the largest power of $2$ that will divide any random concatenation of base $10$ digits of powers of $2$ ending with $2^n$?

My first thought was that it would be $2^n$ itself, for example, if you concatenate $4$ and $2$ to get $42$, that's divisible by $2$ but not by $4$. But whit $2^9 = 512$, you can concatenate $16$ and ...
3
votes
1answer
54 views

Prove by induction $n= qb+r$ for $ n\ge 0$

Let $b$ be a fixed positive integer . Prove by induction for all $ n\ge 0$ there exists $q$ and $r$ non-negative integers ( positive integers + 0) that $n= qb+r$ for $0 \le r < b $ my try its not ...
2
votes
2answers
40 views

Find the number $abc$

The positive integers $N$ and $N^2$ both end in the same sequence of four digits $abcd$ when written in base 10, where digit $a$ is not zero. Find the three-digit number $abc$. $$N \equiv abcd ...
2
votes
1answer
45 views

I suppose this is a familiar number-theoretic operation, but what is it?

Define a function $/\!/ : \mathbb{Z}_{\geq 1} \times \mathbb{Z}_{\geq 1} \rightarrow \mathbb{Z}_{\geq 1}$ as follows: given integers $j,k \geq 1$, we have: $$k/\!/j = \min\{n\in\mathbb{Z}_{\geq 1} : ...
0
votes
2answers
35 views

converting numbers to degree

I have 0 to 1 that represent 0 to 360 degrees I know that 0.5 would represent 180 degrees but what formula would I use to get the other vales for 0 to 1. Thanks
8
votes
3answers
99 views

Minimal $ab$ for Rational Number $a/b$ in an Interval

Given rational numbers $L$ and $U$, $0<L<U<1$, find rational number $M=a/b$ such that $L \le M<U$ and $(a\times b)$ is as small as possible---$a$ and $b$ are integers. For example, If ...
-1
votes
0answers
25 views

Application of Cauchy-Schwartz to an exponential sum involving von Mangoldt function

Let $f(x_1, ..., x_n)$ be a polynomial in $\mathbb{Z}[x_1, x_2, ..., x_n]$. Let $\Lambda$ denote the Von Mangoldt function. Suppose I have an exponential sum of the form $$ S(\alpha) = \sum_{1 \leq ...
1
vote
0answers
69 views
+200

Show that the number of reduced residues $a \mod m$ such that $a^{m-1} \equiv 1 \mod m$ is exactly $\displaystyle \prod_{p \mid m} \gcd(p-1,m-1).$

Show that the number of reduced residues $a \mod m$ such that $a^{m-1} \equiv 1 \mod m$ is exactly $$\displaystyle \prod_{p \mid m} \gcd(p-1,m-1).$$ Suppose $f(x) = x^{m−1}−1$ and let $m = ...
2
votes
1answer
61 views

What is $13^{498}$ (mod $997$)? [duplicate]

I have to determine $$13^{498} \pmod{997}$$ I know that it can only be $1$ or $-1$. But I don't quite know which. How can I decide?
1
vote
1answer
36 views

If $\gcd(a,b)=d$, then $\gcd(a/d, b/d)=1$

So, I think that I understand the proof. The idea is that we want to establish the inequality that says that $c\leq 1$ and with the idea that the $\gcd$ of two numbers is always greater or equal ...
4
votes
2answers
39 views

prove that $n^2 \bmod 4 = 0$ or $1$ for all integers

(Use the fact that every integer is either even or odd to prove that $n^2 \bmod 4 = 0$ or $1$ for all integers) Let $n \in \mathbb{Z}$, then $n$ is either even or odd. Case 1: ($n$ is odd): By ...
3
votes
1answer
40 views

$n^{q}\equiv1~(\text{mod $p$})$ is possible solve this? [closed]

I have the following situation: Let $p, q$ be a prime numbers were $p>q$ and $n\in\{0,1, \ldots, p-1\}$. In this conditions is possible solve (in function of $n$) this equation, ...
2
votes
1answer
41 views

Use Gauss' Lemma to find Legendre symbol $\left(\frac{-1}{n}\right)$ for $n \equiv 1, 3, 5, 7 \pmod 8$.

I know that if $ n \equiv 1 \pmod 4$, then $\left(\frac{-1}{n}\right)=1$, but in this case we are dealing with mod $8$. If $n \equiv 1 \pmod 8$, then $n=1+8k$. So, $(8k+1-1)/2=4k$. So, we have: ...
0
votes
1answer
76 views

Pointy triangles exists

In Yahoo Answers, here, Rita the dog defined a pointy triangle, (more or less) as having three properties. The lengths of two sides are rational and greater than 1. The length of the third side is ...
4
votes
3answers
69 views

prove that if $5| n^2$ then $5|n$ by contraposition

let $ n \in \mathbb{R}$ suppose $5\nmid n$ then by definition of divides n = dk+r where $d \in \mathbb{Z}^{+}$ $k \in \mathbb{Z}$ and $d \neq 5$ and $0 < r \le 5$ Can someone help me finish ...
0
votes
1answer
31 views

Finding the integer parts of irrationals

When working with continued fraction expansions, I sometimes have to calculate the integer part of irrationals quickly without a calculator, what would be an effective way to do this? For example, ...
1
vote
1answer
49 views

Show the congruence $x^{p-1}\equiv 1\pmod{p}$ has $p-1$ solutions

Question: Let $p$ be prime. show the congruence $x^{p-1}\equiv 1\pmod{p}$ has $p-1$ solutions Attempt: I know by Lagrange's theorem that this congruence will have at most $p-1$ solutions since $p-1$ ...
2
votes
2answers
198 views

Parameterization of Natural Numbers

Suppose we have 4 positive integers $a<b<c<d$ such that $a+d=b+c=n$, i.e. $a,d$ and $b,c$ have the same average. Does there exist $p,q,r,s \in \mathbb Z$ such that \begin{equation*} ...
1
vote
2answers
66 views

What does $(n|p)=1$ mean?

My number theory book mentions the following condition: $(n|p)=1$, where $p$ is prime. What does $(n|p)=1$ mean? I used to think $n|p$ implies that $n$ divides $p$.
-1
votes
0answers
9 views

Generate a number set such that the sum of the set details the contents

I have a set of numbers. I want to save space storing my numbers, so I am only interested in the sum of the set (which I assume will require fewer bits to represent than the set). How can I generate ...
3
votes
2answers
47 views

How to prove that if $m$ is squarefree, then $d^2 \lvert mb^2 \implies d \lvert b$

This statement was given in my number theory textbook when analyzing quadratic fields, and I am not seeing how to prove it. $m$ is a squarefree (not divisible by the square of any number) integer and ...
2
votes
1answer
36 views

Hensel's lemma modular arithmatic example problem

In an example for Hensel's Lemma we have met the criteria to use Hensel's lemma and have begun to apply it in a Hensel's iteration. We have $f(x)=x^2+1$ and our initial $x_0=2$ is a solution ...
1
vote
1answer
34 views

$5(a^2+b^2)$ covers all numbers $=a_2^2+a_2^2=b_1^2+b_2^2$?

I start by noting that 4a*2b=2a*4b I write 4a*2b as $((2a+b)+(2a-b))*((2a+b)-(2a-b)) = (2a+b)^2-(2a-b)^2$ I follow a similar principle for 2a*4b which I write as $(a+2b)^2-(a-2b)^2$ to arrive at ...
2
votes
3answers
128 views

Number of ways to express a number as the sum of different integers

Given a number $n$, then $P_k(n)$ is the number of ways to express $n$ as the sum of $k$ integers. For example $P_2(6)=7$ $0+6=6$ $1+5=6$ $2+4=6$ $3+3=6$ $4+2=6$ $5+1=6$ $6+0=6$ Now I worked ...
0
votes
3answers
24 views

Show if $(a,p)=1$ and $x^2\equiv a\pmod{p^2}$ then $(x,p)=1$

Suppose $(a,p)=1$ and $x^2\equiv a\pmod{p^2}$ then $(x,p)=1$ How can I show that this is the case? If $(a,p)=1$ and $x^2\equiv a\pmod{p}$ then is also the case that $(x,p)=1$?
1
vote
1answer
31 views

Number of possible solutions in modular equation

I have given the result value $z$. I know that $$z \equiv x\cdot(x-1)\pmod p$$ where $p$ is prime and the value $p$ is fixed and given. I have also given the information, that $x \in \{m, M\}$, where ...
1
vote
3answers
38 views

Find a possible pair of numbers given HCF and a factor of the LCM

I was just going through a GCSE paper with a student and I came across a question that I'm struggling to find a good method for. The question was this: Martin thinks of two numbers. The ...
0
votes
0answers
30 views

Find all integer solutions to $x^2+y^2=5z^2$ [duplicate]

I'm having trouble with finding the integer solutions to $x^2+y^2=5z^2$. I'm guessing I have to show that $x=y=z=0$ is the only solution. Here's what I have tried... $x=y=z=0$ obviously a solution. ...
5
votes
3answers
67 views

Elementary proof that $-1$ is a square in $\mathbb{F}_p$ for $p = 1 \mod{4}$

I am trying to proof that $-1$ is a square in $\mathbb{F}_p$ for $p = 1 \mod{4}$. Of course, this is really easy if one uses the Legendre Symbol and Euler's criterion. However, I do not want to use ...
0
votes
1answer
57 views

What is wrong with this proof of a number theory competition problem?

Let $a$ and $b$ be positive integers. Suppose $a^n+n| b^n+n$ for any positive integer $n$, prove that $a=b$. My trial: Clearly $b\geq a$, write $b=a+d$, we must show that $d=0$. Now by assumption and ...
1
vote
2answers
62 views

Is there such an integer?

$\{a_n\}_{n=1}^{\infty}$ and $\{b_n\}_{n=1}^{\infty}$ are two infinite sequences of natural numbers such that for all $n$, $0\leq b_n<a_n$. Is it possible to exist an integer $k$ such that for all ...
5
votes
1answer
75 views

Prove $(8k)^{8k}+(8k+1)^{8k+1}$ and $(8k+1)^{8k+1}+(8k+2)^{8k+2}$ are never perfect squares

Prove $$(8k)^{8k}+(8k+1)^{8k+1}\ \ \text{ and } \ \ \ (8k+1)^{8k+1}+(8k+2)^{8k+2}$$ are never perfect squares ($k\ge 1$). mod $8$ gives $1$ for both, which is a quadratic residue, so doesn't ...
2
votes
2answers
41 views

Number Theory - Sum of Squares and Quadratic Residue

Show that if $p$ is a prime number satisfying $p\equiv 1\mod 4$, $a$ is an odd positive number, and there exists $b$ such that $a^2+b^2=p$, then $a$ is a quadratic residue $\mod p$. I know that ...
1
vote
2answers
26 views

Show $x^2+2x+1\equiv 27 \;\text{mod}\; 61$ is solvable and find the number of solutions.

I'll show how far I have got: $$x^2+2x+1\equiv 27 \;\text{mod}\; 61$$ $$(x+1)^2\equiv 27\; \text{mod} \; 61$$ So we need to find the Legendre symbol value for $$\begin{pmatrix} 27\\ 61 \end{pmatrix}$$ ...
3
votes
4answers
44 views

Find the following integer $ x $, s.t. $x \equiv 7^{57} \pmod {133}$

Find the following integers $x$: $x \equiv 7^{57} \mod 133$ I need to use fermat's little theorem for this problem which I know. It is for a prime number p. Then $a^{p-1} \equiv 1 \pmod p$ but I do ...
1
vote
2answers
22 views

When is $2$ a quadratic residue mod $p$?

For which prime numbers $p$, is $2$ a quadratic residue modulo $p$. I know that $2$ is a quadratic reside iff $$2^{\frac{p-1}{2}} =1 \; \bmod \;(p) $$ so $$2^{p-1} =1 \; \mod \; (p). $$ But I ...
4
votes
2answers
34 views

Let $n$ be an integer. If $(a,m)=1$, there exists an integer $a'$ such that $a'\equiv a \pmod{m}$ and $(a',n)=1$.

Let $n$ be an integer. If $(a,m)=1$, there exists an integer $a'$ such that $a'\equiv a \pmod{m}$ and $(a',n)=1$. I am not sure if the above statement is true. It has been annoyingly elusive to ...
0
votes
2answers
16 views

A question in Number Theory about Euler Theorem/Fermat little theorem

I tried to solve this question but without a success. for every prime number $$p\ge7 $$ and every $$n \in \mathbb N$$ : $$10^{n(p-1)}\equiv 1 (\text{mod }9p) $$ I tried to use Euler theorem. but It ...
1
vote
1answer
63 views

The following is a necessary condition for a number to be prime, from its digit expansion. Has it been referred somewhere?

Concerning a numbers’ digits we know some necessary conditions on them for the number to be prime, besides the last digit having to be odd (except for prime 2). For example in decimal representation ...
2
votes
4answers
27 views

Prove that if $p\ge 7$ then $\exists n\in\Bbb{Z}$ such that $10^{n(p-1)}\equiv1 \mod 9p$.

Prove that if $p\ge 7$ then $\exists n\in\Bbb{Z}$ such that $10^{n(p-1)}\equiv1 \mod 9p$. Edit: $p$ is prime, of course. I tried using theorems regarding Euler, but I can't seem to arrive at something ...
0
votes
1answer
52 views

If you know $N=a^2+b^2$ how to compute $a$ and $b$ for large $N$?

Having tested that $N$ is such that every exponent of a prime in the prime factorisation of $N$ congruent to $3 \bmod 4$ is even. Then for large $N$ can we find $a$ and $b$, such that ...
5
votes
1answer
221 views
+50

Increasing sequence of divisors of a quadratic trinomial

This question is from a Russian contest, the 2011 Tuymaada Olympiad. It's the fourth question on day two for the problems at grade level 2. Let $P(n)$ be a quadratic trinomial with integer ...
1
vote
2answers
28 views

if d divides n then prove that fibonacci of d divides fibonacci of n

prove that if $d$ divides $n$ then prove that fibonacci of $d$ divides fibonacci of $n$. i have tried to write $F(n)$ as a multiple of $F(d)$ using the fact that $n = ad$ for some natural $a$ but got ...