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

learn more… | top users | synonyms (1)

-3
votes
0answers
36 views

Eulers Phi Function [closed]

I need help with Verify that Eulers phi function gives a result of $40$ when applied to the numbers $75$. I know that $\phi(40) = 16$, $\phi (75) = 40$ Please help?
3
votes
0answers
64 views

Making $66$ with $1,1,1,1,1$

How can one make $66$ with only $1,1,1,1,1$? You cannot combine these two numbers to make a new number, such as this: $66=11 \times (1+1+1)!$. This was inspired a game of dice that I used to play, ...
1
vote
2answers
26 views

Find all incongruent solutions to $21x \equiv 14 \pmod{91}$

Find all incongruent solutions to $21x \equiv 14 \pmod{91}$. I am able to work out the solution using Euclidean algorithm techniques, but the signs on the expression do not match up with the initial ...
1
vote
1answer
23 views

find all incongruent solutions to $x^2 \equiv 3$ (mod$7$) [closed]

find all incongruent solutions to $x^2 \equiv 3$ (mod$7$) The only theorems I have learned to use in this scenario are the linear equation thm: $ax + by = gcd(a,b)$ and linear congruence thm. With ...
1
vote
1answer
41 views

Which function satisfy $f'(\mathbb{N}) \subseteq \mathbb{N}$

I was thinking and found the following question : Let $f:\mathbb{R} \to \mathbb{R}$ a differentiable function and consider the restrictions $f|_\mathbb{N}$ and $f'_\mathbb{N}$ i) Which functions ...
1
vote
1answer
36 views

Last 3 digits of Marsenne numbers

Marsenne numbers are of the form $2^{p} - 1$, $p$ is a prime. Last $3$ digits can be obtained from $2^{p} - 1 \equiv x \pmod {1000}$. This is equivalent to $$2^{p} - 1 \equiv x_1 \pmod 8\tag1$$ and ...
0
votes
0answers
11 views

Involutary Keys for Shift Cipher

Let $e_K(x)=(ax+k)\mod m$ and $d_K(x)=a^{-1}(x-k)\mod m$, where $K=(k,a)$ How can I show that $e_K(x)=d_K(x)$ if and only if $k^{-1}=k\mod m$ and $a(k+1)=0\mod m$?
6
votes
1answer
83 views

A Increasing Multiplicative Functional Equation where $nm$ is a cube

Let $f:\mathbb{N}\rightarrow\mathbb{N}$ be a strictly increasing function such that $$f(2)=2$$ and $$f(mn)=f(m)f(n)$$ for all positive integers $m,n$ such that $mn$ is a perfect cube. ...
0
votes
0answers
36 views
+50

Range of inverse harmonic mean of two integers

Today I was solving an exercise and one of the things I tried (which later turned out to be useless) involved considering the following: Is there a simple way to describe in terms of $n$ the range of ...
0
votes
0answers
20 views

How to find max $c$ that solve $N \mod p^c = 0$

The title provide 100% of my question, below is explanation to why am I asking this. I been reading about the quadratic sieve article in wiki, the part where sieve is actually performed. The goal of ...
2
votes
2answers
31 views

How to find a solution knowing that gcd(512 , 200) = 8c ?

i got this for homework , but i would like to know if i'm just supposed to substitute any value i want for c and , find a solution? Or am i to use c as an arbitrary value , and find a solution which ...
4
votes
5answers
159 views

Looking for a non-combinatorial proof that $a! \cdot b! \mid (a+b)!$

(I use $a$ and $b$ to denote natural numbers.) Question. Without appealing to the combinatorial interpretation of $$\frac{(a+b)!}{a! b!}$$ as a multinomial coefficients, is there a proof that for ...
1
vote
2answers
84 views

Using binomial theorem to prove $a | b^n \Rightarrow a | b$. ( | is divides, a prime, n integer > 1)

I tried expanding $(b-a+a)^n=$[$(b-a)+a$]$^n$ but it just seemed to further complicate the problem. I also tried to prove the contrapositive but that doesn't seem to lead to anywhere to. Is there any ...
0
votes
1answer
23 views

Modulus Notation Division

I have a couple of silly questions (it will definitely demonstrate my lack of ability in mathematics :P) Is there a type of reduction or absorption of modulus in congruence equations? Here's an ...
0
votes
1answer
27 views

Show that the linear Diophantine equation has infinitely positive solutions [closed]

Any ideas on how to write down this proof? Let a and b be positive integers and assume $\gcd(a,b)|c$. Show that the linear Diophantine equation $ax-by=c$ has infinitely many positive solutions x,y.
0
votes
2answers
55 views

How to find total number of sum of consecutive number of $n$? [duplicate]

How many ways are there to write $n$ as the sum of consecutive positive integers? Example: $15$ has $3$ consecutive sums: $1+2+3+4+5=15$ $7+8=15$ $4+5+6=15$
0
votes
1answer
33 views

Divisibility criteria

Notice that by $\mod 7$ we have $$6!\equiv -1 (\mod 7)$$ $$5!1!\equiv 1 (\mod 7)$$ $$4!2!\equiv -1 (\mod 7)$$ $$3!3!\equiv 1 (\mod 7).$$ Calculate $10!, 9!1!, 8!2!, 7!3!, 6!4!, 5!5!$ by ...
5
votes
3answers
96 views

The only positive integers that divide successive numbers of the form $n^2+3$ are $1$ and $13$

I stuck with this problem, I don't know how to start with. Prove that the only positive integers that can divide successive numbers of the form $n^2+3$ are 1 or 13.
0
votes
2answers
51 views

Legendre symbol, what is it?

I am reading wiki article about Legendre symbol and I don't understand the power meaning. Can you please explain the next expression. $$\left(\frac ap\right)\equiv a^{\frac{p-1}{2}}\pmod p$$
19
votes
2answers
2k views

Find a thousand natural numbers such that their sum equals their product

The question is to find a thousand natural numbers such that their sum equals their product. Here's my approach : I worked on this question for lesser cases : \begin{align*} &2 \times 2 = 2 + ...
-2
votes
1answer
45 views

Dealing with phi function property

If $n=2^kN$, where $N$ is odd, then $$\sum_{d\mid n}(-1)^{n/d}\phi(d)=\sum_{d\mid 2^{k-1}N}\phi(d)-\sum_{d\mid N}\phi(2^kd)$$ I have no idea how to seperate things inside the left side. In a ...
1
vote
2answers
59 views

Quadratic reciprocity: Tell if $c$ got quadratic square root mod $p$

I am reading the wiki article about Quadratic reciprocity and I don't understand how can I tell if some integer $c$ got quadratic root mod $p$? So far I am using brute search to find $y$ such that ...
1
vote
0answers
32 views

Different representation of $f(n) = \sum_{d|n; \ \sqrt n\le d \le n}(-1)^d$

I am looking for a different way to calculate the following sum where $d,n\in \mathbb N$: $$f(n) = \sum_{d|n; \ \sqrt n\le d \le n}(-1)^d$$ Here are some example results for different values of n ...
7
votes
4answers
132 views

Find the remainder when ${{5^5}^5}^5$ is divided by $24$

Find the remainder when ${{5^5}^5}^5$ is divided by $24$ I tried using congruence modulo. $$5^2\equiv1\mod{24}$$ $$5^5=125\mod{24}$$ But this does not give the correct answer.
1
vote
1answer
50 views

Find all functions $f:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$ [closed]

Find all functions $f:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$, such that $i)f(a,a)=a$ $ii)f(a,b)=f(b,a)$ $iii)\mbox{If } a>b, \mbox{then } f(a,b)=\dfrac{a}{a-b}f(a-b,b)$ For the form of the ...
2
votes
1answer
46 views

How can all of them be irrational ??

Assume that $\{x,y,x^2,y^2,xy\}$ are all irrational. Can it be true that all of $\{x-y,x+y,x^2-y^2,x^2+y^2\}$ are irrational? Details: $|x|\ne|y|$ and $x,y\in\mathbb R$. In the ...
3
votes
3answers
52 views

How to prove $10^n$ is the smallest $n+1$ digit number?

It seems obvious that $10$ is the smallest 2 digit number and $100$ is the smallest 3 digit number. In fact, it seems a little obvious to me that $10^n$ is the smallest $n+1$ digit number. But how ...
0
votes
3answers
72 views

Remainder of $98!$ modulo $101$

My question is: What would be the remainder when $98!$ would be divided by $101$? Though this question is very easy but I'm a little confused about my concepts. I have found multiples of $2$ and ...
0
votes
0answers
23 views

Linear equations and the gcd

given integers $a$ & $b$ it can be shown that the equation: $$ax + by = gcd(a,b)$$ always has a solution. To prove this we assume the exitence of two solutions $$(x_1, y_1)$$ & $$(x_2, y_2)$$ ...
0
votes
1answer
27 views

tips for proving infinity composite numbers

Prove infinity composite numbers of the form (n-1)!+1. What tips can you give me on how to look at this problem? I only proved infinity primes but never infinity composite numbers. At this moment, ...
-6
votes
1answer
86 views
1
vote
0answers
12 views

Number of Solutions to a Linear Equation Mod N

Is there a formula for the number of solutions to $$a_1x_1+\dots+a_nx_n \equiv 0 \mod{N}$$ such that $(x_i,N)=1$ in terms of the coefficients $a_1,\dots,a_n$? Clearly, by Chinese Remainder Theorem, ...
2
votes
1answer
35 views

Numbers written as $a^b+b$ for $a,b\geq 2$

Is there a sequence of $102$ consecutive positive integers, among which exactly $100$ satisfy the property that they can be written as $a^b+b$ for some integers $a,b\geq 2$? This looks somewhat ...
0
votes
1answer
30 views

Solving $\sqrt[3]{7x^2-13xy+7y^2}=|x-y|+1$ in integers

Find all pairs $(x,y)$ of integers such that $$\sqrt[3]{7x^2-13xy+7y^2}=|x-y|+1.$$ Since $x,y$ are symmetric, we can assume $x\geq y$, so the right-hand side is $x-y+1$. If $x=y$, the equation ...
3
votes
1answer
46 views

$ord_p(x)$ -Units and Irreducibles

Let $p$ be a prime number in $\mathbb{Z}$. Let $R = R_p = \{x \in \mathbb{Q}\ |\ ord_p(x)\geq0\}$, which is a subring of $\mathbb{Q}$. (a) Show that $x \in R$ is a unit iff ...
3
votes
3answers
51 views

Show that if $a$ and $b$ are positive integers then, $(a!)^b \cdot (b!)\mid (ab)!$

Show that if $a$ and $b$ are positive integers then, $(a!)^b \cdot (b!)\mid(ab)!$. Which is equivalent to prove that $(a!)^b\mid (b+1)(b+2) \cdots (ab)$
1
vote
2answers
22 views

Modulus operation finding value sattisfying given condition

Find the minimum value of $p$ such that $5^p \equiv 1 \pmod p$. What is the approach to solve such questions?
3
votes
2answers
30 views

If $p\equiv3 \pmod4 $, then there does not exist any integer $x$ with $x^2 ≡ −1 \pmod p$.

Suppose that $p$ is a prime number that that $p\equiv3 \pmod4 $. Prove that there does not exist any integer $x$ with $x^2 ≡ −1 \pmod p$. I am looking to use Fermat's Little Theorem but not able ...
0
votes
1answer
27 views

Determine all the positive integers $n\geq 3$, such that $1+{n\choose 1}+{n\choose 2}+{n\choose 3}\vert 2^{2000}$

Determine all the positive integers $n\geq 3$, such that $$1+{n\choose 1}+{n\choose 2}+{n\choose 3}\vert 2^{2000}$$ Any hint please!!, I prove that ${n\choose 3}+{n\choose 2}={n+1\choose 3}$ and ...
1
vote
3answers
431 views

Why is the Axiom of Infinity necessary?

I am having trouble seeing why the Axiom of Infinity is necessary to construct an infinite set. According to a professor of who's mine teaching a class on "infinity," the Peano axioms are only ...
1
vote
2answers
54 views

Solving $12x \equiv 20 \pmod{38}$

$12x \equiv 20 \pmod{38}$ $gcd(12,38)=2$ using Euclidean Algorithm. There is a solution since $2|20$. Use the Extended Euclidean Algorithm $2=12*-3 +1*38$ Then $20=2*10=12*-3*10+1*38*10$ so ...
3
votes
3answers
43 views

If $\gcd(A,B,C)=1$, can we find $h$ s.t. $\gcd(A,hB)=1$?

If $\gcd(A,B,C)=1$, can we find $h$ s.t. $\gcd(A,B+hC)=1$? I have tried but I find I am not able to prove this. Maybe I do not know some important thing? Could someone help? Thanks!
0
votes
2answers
63 views

I need a ratio of numerator below 36 to get to closest the following ratio of 38/45 =0.84444444

It is a trivial question to get a ratio in whole numbers. The numerator has to be below or equal to 36 and the denominator below 48. You have to avoid single digits and the best prefered solution is a ...
0
votes
1answer
65 views

Suppose that $n$ is a factor of $(n-1)!+1$. Prove that $n$ is prime [duplicate]

This is in an Algebra and Combinatorics module and I don't know how to prove this. The full question is, Let $n$ be a natural number greater than $1$. Suppose that $n$ is a factor of $(n-1)!+1$. ...
0
votes
1answer
19 views

Quadratic residues and euler equation

Let $p$ be an odd prime and let $(a,p)=1$. There is no guaranteed that there is a solution to $$x^2\equiv a \pmod p$$ What is wrong here: $$a^{(p-1)/2}≡(x^2)^{(p-1)/2}\equiv x^{p-1} \pmod p$$ It is ...
-1
votes
0answers
30 views

Do $p=2617$ and $q=3571$ have modular multiplicative inverse with $e = 17$?

I need multiplicative inverse of $17 \mod \left(\phi(p) \cdot \phi(q)\right)$. They are both prime, the totient of the product is $2616 \cdot 3570 = 9339120$. But $17$ is a factor of $9339120$, ...
3
votes
2answers
58 views

Is the last digit of this number :$ {{4^4}^n}+1 $ always $7 $ for $n>1$ and could this be prime?

Some computations in wolfram alpha for $n=2,3,4,5 ,6$ showed that the last digit of this number $ {{4^4}^n}+1 $ for $n>1$ always $7$ . My question here :How do I know if it's last digit always ...
17
votes
3answers
898 views

Prove that the number 14641 is the fourth power of an integer in any base greater than 6?

Prove that the number $14641$ is the fourth power of an integer in any base greater than $6$? I understand how to work it out, because I think you do $$14641\ (\text{base }a > 6) = ...
2
votes
0answers
22 views

How do i show this :$\lim_{k\to\infty} \frac{\sigma_{2k+1}(n)}{\sigma_{2k-1}(n)}=n²$ if it is true?

I run some computation in wolfram alpha I find for many fixed values of $n$ and for an arbitrary integer $k$ the ratio : $\frac{\sigma_{2k+1}(n)}{\sigma_{2k-1}(n)}$ close to $n²$ . My question here ...
0
votes
3answers
32 views

Divisibility of integer numbers

If we have two integers $a$ and $b$ such that $a = \frac{5b}{6}$, is $a$ divisible by $5$? If so, why is that? I don't see it.